1629 Movie Festival - CSES 最大不相交区间数
P1250 种树 - 洛谷
这两类问题的关键都是按右端点升序排序后进行处理。
最大不相交区间数
题意：给定 \(n\) 部电影的起始时间，问最多可以完整的看我几部？
每次选择右端点结束时间最早的区间，为剩下的区间留下更多空间。
注意题目要求区间的端点算法可行。如果区间为 [1, 3] 和 [3, 5] 答案是算两次的。而区间选点的话这里往往只选一个点，即 3 。
具体代码为
import sys
from math import inf
if 1:inp = lambda: sys.stdin.readline().strip()II = lambda: int(inp())MII = lambda: map(int, inp().split())LII = lambda: list(MII())Max = lambda x, y: x if x > y else yMin = lambda x, y: x if x < y else ydef main():n = II()t = []for _ in range(n):s, e = MII()t.append((s, e))t.sort(key=lambda x: x[1])cnt = 1r = t[0][1]for x in t[1:]:if x[0] >= r: # 注意这里理解清楚题意cnt += 1r = x[1]print(cnt)if __name__ == "__main__":main()
区间选点
如果仅仅是每个区间都要有点的话，那问题就等价于最大不相交数了。否则需要额外分析。
题意：地区被分成 \(1,2,\cdots n\) 块，每块只能种一颗树。居民希望在 a, b 间至少种 \(c\) 棵树，问最少需要种多少棵树才能满足要求。
枚举每一个区间，如果当前区间没有满足需求就从右端开始种到满足需求为止。
# 模版代码直接复制即可
def main():n = II()m = II()t = []for _ in range(m):a, b, c = MII()t.append((a, b, c))t.sort(key=lambda x: x[1])used = [0] * (n + 1)ans = 0for a, b, c in t:cnt = sum(x for x in used[a:b+1])if cnt < c:need = c - cntfor i in range(b, a - 1, -1):if used[i] == 0:used[i] = 1ans += 1need -= 1if need == 0:breakprint(ans) if __name__ == "__main__":main()
相关习题
H - Temperature of Bath - AtCoder 区间选点，等价于最大不相交区间数
B4399 蓝桥杯青少年组国赛 2025 第四题 - 洛谷