如何用贪心算法求B001区间选点最大不相交区间数？

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 y Min = lambda x, y: x if x < y else y def main(): n = II() t = [] for _ in range(n): s, e = MII() t.append((s, e)) t.sort(key=lambda x: x[1]) cnt = 1 r = t[0][1] for x in t[1:]: if x[0] >= r: # 注意这里理解清楚题意 cnt += 1 r = 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 = 0 for a, b, c in t: cnt = sum(x for x in used[a:b+1]) if cnt < c: need = c - cnt for i in range(b, a - 1, -1): if used[i] == 0: used[i] = 1 ans += 1 need -= 1 if need == 0: break print(ans) if __name__ == "__main__": main() 相关习题 H - Temperature of Bath - AtCoder 区间选点，等价于最大不相交区间数 B4399 蓝桥杯青少年组国赛 2025 第四题 - 洛谷