区间调度
选择最多两两不相交的区间;按右端点升序,能选就选,交换论证给出最优性。标签 贪心 / 区间 / 排序 / 交换论证
题目描述
给定 个区间 。两个区间 相交,当且仅当 且 。端点相接不算相交。求最多能选出多少个两两不相交的区间。
,。
题解
按右端点 升序排序。维护上一次选中区间的右端点 ,初始为 。
依次扫描每个区间:
- 若 ,选中它,并令 ;
- 否则跳过。
正确性用交换论证。把所有区间按右端点排序,取一个最优解并按右端点排序,设其第一个区间为 。贪心选出的第一个区间 右端点最小,因此 。最优解中其余区间都与 不相交,所以它们的左端点不小于 ,从而也不小于 ;把 换成 仍得到最优解。归纳即可。
复杂度
排序为 ,扫描为 ;空间为 。
参考
- 经典活动安排问题(CLRS 活动选择)。
- 同型题:Luogu P1803 线段覆盖。