题意

给定若干比赛的开始时间和结束时间。参加一个比赛必须完整参加，不能同时参加两个比赛。问最多能参加几个比赛。

思路

经典区间调度贪心：按结束时间从早到晚排序。

扫描排序后的比赛，如果当前比赛的开始时间不早于上一个已选比赛的结束时间，就选择它。

为什么这样对？结束越早，留给后面比赛的时间越多。若某个最优方案当前选了一个结束更晚的可选比赛，可以把它替换成结束更早的比赛，不会减少后续可选空间。

Python 知识

• 把区间保存成 (end, start)，直接 sort() 就按结束时间升序排列。
• sys.stdin.buffer.read().split() 适合 n 最大到 10^6 的大量整数输入。
• 扫描时只维护 last_end 和答案数量，不需要保存选择列表。

参考笔记：

• /home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md
• /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]

matches = []
index = 1
for _ in range(n):
    start = data[index]
    end = data[index + 1]
    matches.append((end, start))
    index += 2

matches.sort()

answer = 0
last_end = 0
for end, start in matches:
    if start >= last_end:
        answer += 1
        last_end = end

print(answer)

复杂度

排序时间复杂度为 $O(n\log n)$，扫描为 $O(n)$，空间复杂度为 $O(n)$。

总结

区间覆盖/区间调度中，“最多选不相交区间”通常优先考虑按右端点排序的贪心。