Activity Selection Problem
活动 i 从时间 start[i] 持续到时间 finish[i]。一个人一次只能进行一项活动，下一项活动必须在上一项活动结束后才开始：如果某项活动恰好在另一项活动结束的时间开始，就不能接在它后面。
返回一个人能进行的最大活动数量。
函数
- startinteger-array
- 每项活动的开始时间
- finishinteger-array
- 每项活动的结束时间；finish[i] 对应 start[i]
- 返回值integer
- 一个人连续完成的活动数量最多
约束条件
1 ≤ start.length == finish.length ≤ 50000 ≤ start[i] ≤ finish[i] ≤ 105- 一项活动可能同时开始和结束。这些数组没有排序。
示例
- 输入
- start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
- 输出
- 4
- 解释
- 执行 10 到 13、14 到 19、21 到 22 和 25 到 30，可得到 4。无法得到 5：10 到 13 与 12 到 16 冲突，21 到 22 与 20 到 24 冲突。
- 输入
- start = [1, 5, 9]finish = [5, 9, 12]
- 输出
- 2
- 解释
- 从 5 到 9 的活动在第一个活动结束的准确时间开始，因此不能接在它后面。先进行从 1 到 5 的活动，再进行从 9 到 12 的活动是可行的，因此答案是
2。
- 输入
- start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
- 输出
- 3
- 解释
- 从 0 到 100 的活动与其他所有活动都重叠。去掉它后，2 到 4、5 到 7 和 8 到 10 可以依次排列：
3。
进阶
现在有两个人并行工作，每次各自做一项活动。他们可以同时做多少项活动？每项活动应该由谁来做？
提示
逐个打开提示，每个都会多透露一点。
假设你已经知道自己先做哪项活动。你希望先做哪一项，这样之后能剩下尽可能多的时间？
最早结束的活动始终是安全的首选：以其他活动开始的计划，都可以将它换成最早结束的活动，并保持活动数量不变。之后，对于在它结束后开始的活动，也会重复同样的问题。
按结束时间对活动排序，并将每个活动的开始时间与结束时间一起移动。遍历排序后的列表，同时记录你上一个选定活动的结束时间，并选择开始时间严格晚于该时间的所有活动。
题解
尝试所有活动子集需要指数级时间。只需采用一条贪心规则，就能解决这个问题：在仍然能安排的活动中，始终选择最早结束的活动。按结束时间排序后，只需遍历一次即可应用这条规则。
一次又一次地选择最早结束的
结果正确，但无法在最大的测试中运行完毕
思路
最早结束的活动至少和其他任何活动一样适合作为第一个选择。它不会让你更晚释放时间，因此，任何能接在其他第一个选择之后的活动，也都能接在它之后；把其他选择换成它，活动总数不变。选好这个活动后，问题就会在所有开始时间晚于它结束时间的活动中重复出现。
在第一个示例中，你先选 10 到 13，然后选 14 到 19，再选 21 到 22，最后选 25 到 30：共 4 个。
每次选择都要扫描全部 n 个活动，因此耗时是 n 乘以答案。当全部 5000 个活动都能依次安排时，需要检查 2500 万次。
算法
- 在每个开始时间下面设置
count = 0和lastFinish = -1。 - 扫描所有活动，找出满足
start[i] > lastFinish且结束时间最早的活动。 - 如果没有这样的活动，就返回
count。 - 否则，将
count加 1，把lastFinish设置为该活动的结束时间，然后再次扫描。
def maxActivities(start, finish):
n = len(start)
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
while True:
# among the activities that start after last_finish, find the one that ends first
pick = -1
for i in range(n):
if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
pick = i
if pick == -1:
return count
count += 1
last_finish = finish[pick]按结束时间排序并采用贪心策略
思路
按结束时间排序一次后，你遇到这些活动的顺序就和上面的扫描查找它们的顺序一致。遍历排序后的列表，同时记录 lastFinish，也就是你上一个选中活动的结束时间。如果某个活动的 start[i] > lastFinish，它就是仍然符合条件且结束时间最早的活动，因此选中它。其他活动都会与你上一次的选择冲突，所以跳过它们不会有损失。
排序后，第一个示例依次是 10 到 13、12 到 16、14 到 19、21 到 22、20 到 24、25 到 30。你会选中第一个、第三个、第四个和第六个：12 不晚于 13，20 也不晚于 22。
结束时间相同的情况不需要额外规则。一旦你选中一个在 t 时结束的活动，其他所有在 t 时结束的活动，其开始时间都在 t 时或之前，因此会被跳过。
算法
- 按
finish对活动排序，并将每个活动的开始时间与其结束时间一起移动。 - 设置
count = 0和lastFinish = -1。 - 按此顺序遍历每个活动，如果
start[i] > lastFinish，则将count加 1，并设置lastFinish = finish[i]。 - 返回
count。
def maxActivities(start, finish):
order = sorted(range(len(start)), key=lambda i: finish[i]) # earliest finish first
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
for i in order:
if start[i] > last_finish:
count += 1
last_finish = finish[i]
return count
易错点和边界情况
- 按开始时间排序。在第三个示例中，0 到 100 最先开始，并挡住了另外三项活动。
- 先选最短的活动。对于 1 到 5、5 到 6 和 6 到 10，最短的是 5 到 6，它与另外两项活动都冲突；选择 1 到 5 和 6 到 10 可以得到 2。
- 使用
≥而不是>进行比较。在第二个示例中，这会返回 3 而不是 2。 - 单独对
finish排序。每个开始时间都必须与自己的结束时间一起移动，否则开始时间就会与错误的活动配对。 - 将
lastFinish初始化为 0。这样，单独一项从 0 到 1 的活动会被跳过，因为0 > 0为 false。
常见问题3
活动选择问题的时间复杂度是多少？
按结束时间排序需要 O(n log n)，之后的贪心遍历需要 O(n)，因此排序是主要耗时。如果活动已经按结束时间排好序，只需遍历一次，就能在 O(n) 时间和 O(1) 额外空间内解决问题。
什么是 N 场会议安排在一个会议室的问题？
这是同一个问题，只是换成了会议场景：一个会议室，N 场会议，并且每场会议只能在上一场结束后开始。按结束时间对会议排序，然后选择每场开始时间晚于上一场已选会议结束时间的会议。要列出这些会议，请记录每场选中会议的索引；结束时间相同时，选择索引较小的会议。
活动选择问题是动态规划问题吗？
可以，但不一定需要。按结束时间排序的活动表中，记录以每个活动结束的活动集合所能包含的最多活动数量，可以在 O(n²) 时间内得到答案。贪心选择始终是安全的，因此只需遍历一次。当活动带有值，且你要最大化它们的总值时，表格就成了合适的工具。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def maxActivities(start, finish):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
start = [10, 12, 20, 14, 25, 21] finish = [13, 16, 24, 19, 30, 22]
预期输出
4