区间调度

选择最多两两不相交的区间;按右端点升序,能选就选,交换论证给出最优性。

标签 贪心 / 区间 / 排序 / 交换论证

题目描述

给定 𝑛 个区间 [𝑙𝑖,𝑟𝑖]。两个区间 𝑖,𝑗 相交,当且仅当 𝑟𝑖>𝑙𝑗 且 𝑟𝑗>𝑙𝑖。端点相接不算相交。求最多能选出多少个两两不相交的区间。

1≤𝑛≤105,0≤𝑙𝑖<𝑟𝑖≤109。

题解

按右端点 𝑟𝑖 升序排序。维护上一次选中区间的右端点 𝑅,初始为 −∞。

依次扫描每个区间:

  • 若 𝑙𝑖≥𝑅,选中它,并令 𝑅←𝑟𝑖;
  • 否则跳过。

正确性用交换论证。把所有区间按右端点排序,取一个最优解并按右端点排序,设其第一个区间为 𝑜。贪心选出的第一个区间 𝑔 右端点最小,因此 𝑟𝑔≤𝑟𝑜。最优解中其余区间都与 𝑜 不相交,所以它们的左端点不小于 𝑟𝑜,从而也不小于 𝑟𝑔;把 𝑜 换成 𝑔 仍得到最优解。归纳即可。

复杂度

排序为 𝑂(𝑛log𝑛),扫描为 𝑂(𝑛);空间为 𝑂(𝑛)。

参考

源码位置