《Interval Coverage》题目分析

这道题属于一类很常见的区间处理题目。

具体来说，可以用以下贪心思路解决本题：

首先找到一个起点 <= X，并且终点尽量大(靠右)的区间，选为第一个区间。不妨设这个区间的终点是R[1]。

然后再找一个起点 <= R[1]，并且终点尽量大的区间，选为第二个区间。不妨设这个区间的终点是R[2]。

重复以上步骤，直到某个R[k]满足R[k] >= Y，这时R[1] ... R[k]即是一组最优的区间，k即是答案。

如果在中间某一步发现R[k] == R[k-1]，说明做不到覆盖整个[X, Y]，输出-1。

以上贪心算法最关键的就是找起点 <= 某个值，同时终点尽量大的区间。

我们可以将所有区间按起点排序，然后从头到尾扫描即可完成以上的查找。复杂度是排序O(NlogN) + 扫描贪心O(N)。