区间覆盖
进阶区间覆盖贪心地每次选能延伸最远的区间。
// 算法讲解
区间覆盖
输入偶数个整数：区间起点、终点交替。目标覆盖 [0, 10]。
待机
速度 中
待机 ⌨1int intervalCover(int L, int R, vector<pair<int,int>>& segs) {
2 sort(segs.begin(), segs.end());
3 int cur = L, cnt = 0, i = 0, n = segs.size();
4 while (cur < R && i < n) {
5 int farthest = cur;
6 while (i < n && segs[i].first <= cur) {
7 farthest = max(farthest, segs[i].second);
8 i++;
9 }
10 if (farthest == cur) return -1;
11 cur = farthest;
12 cnt++;
13 }
14 return cur >= R ? cnt : -1;
15}
复杂度分析
时间 O(n log n)
空间 O(n)
最优 O(n) 已排序时
最坏 O(n log n)
算法讲解
区间覆盖问题给定一个目标区间 [L, R] 和若干候选区间，要求用最少的候选区间覆盖目标。
贪心策略：从左端 L 出发，每次选择左端不超过当前覆盖右界、且右端延伸最远的区间。
如果某一轮找不到能继续延伸的区间，则覆盖不可能完成。
正确性源于"多覆盖不亏"：在满足左端约束的条件下，右端越远，给后续步骤留下的余地越大。