[贪心算法] 区间问题归纳

基本定义

区间用一个结构体来表示：

struct Internal {
    int l, r;
    bool operator < (const Internal& rhs) const {
        return ......; // 按左端点 或 右端点 或其它排序
    }
};
vector<Internal> vec; // 存放所有区间的容器

以下代码只使用一个int类型的ans进行计数，若题目需要打印出所选择的区间/点，则改成用一个vector类型的ans存储即可。

一、区间不相交问题

1. 定义

数轴上有n个区间（li, ri），选择尽量多的区间，使得这些区间两两不相交。

2. 解析

贪心策略：按r从小到大进行排序，即总是先选取r小的区间，这样就能给后面的区间留下更多空间。

当r相等时，l无所谓，因为只要选择其中不与前一个区间相交的任意一个即可。

3. 模板

sort(vec.begin(), vec.end());  // 按r排序
int ans = 0, cur = -INF;  // cur表示当前已选择的最大右端点
for(const auto & p : vec) if(p.l >= cur) ans ++, cur = p.r;

4. 例题

UvaLive 6606：https://blog.nowcoder.net/n/55899ecc076a4580b5154adf3e6d5f77

二、区间选点问题

1. 定义

数轴上有n个区间[li, ri]，选择尽量少的点，使得每个区间内都至少有一个点。

2. 解析

贪心策略：按r从小到大进行排序。每次选点时，总是选取第一个不被包含的区间的最右端点处。这样能让这个点接触到最多区间。

当r相等时，l无所谓，因为不影响点数。

3. 模板

sort(vec.begin(), vec.end());  // 按r排序
int ans = 0, cur = -INF;  // cur表示当前已选择的最右的点
for(const auto& p : vec) if(cur < p.l || cur > p.r) ans ++, cur = p.r;

4. 例题

Uva 1615：https://blog.nowcoder.net/n/533e51de360e47989013da008947bd11

三、区间覆盖问题

1. 定义

数轴上有n个区间[li, ri]，选择尽量少的区间覆盖一条指定线段[s,t]。

2. 解析

贪心策略：按l从小到大进行排序。将l<s的这些区间的小于s的部分截掉（因为这部分没有用），然后从这些区间中选择出剩余长度最长的进行覆盖，然后将s更新为该区间的右端点。接下来继续遍历以此类推，直到s>=t，说明已经覆盖完毕。

这道题贪心策略稍微复杂，代码写起来也稍微麻烦，要好好记忆。

3. 模板

sort(vec.begin(), vec.end());  // 按l排序
int s = 0, t = M, ans = 0;  // 目标区间[s,t]
auto L = vec.begin();
while(s < t && L != vec.end()) {  // 右端点无法覆盖
    auto R = upper_bound(L, vec.end(), Internal(s, s));  // [L,R)表示容器下标范围
    if(L == R) break;  // 左端点无法覆盖
    auto chosen = *max_element(L, R, [](const Internal& a, const Internal& b) {
        return a.r < b.r;
    });  // 找到最长的那个
    ans ++;
    L = R, s = chosen.r;
}

if(s < t) cout << -1 << endl;  // 无法覆盖完全

4. 例题

Uva 10020：https://blog.nowcoder.net/n/922860bcfe724bdc8ced0de456766754

四、区间限制问题之用时相等

1. 定义

有若干个任务，每个任务有一段执行的时间区间[li, ri]限制，每个任务的用时都相等，比如都为1。
问能否完成所有任务。

2. 解析

贪心策略：按r从小到大进行排序（r相等时，按从长到短排序），每次尽量早地执行任务（可能就是从l开始，也可能不是，因为被之前的任务占用）。这里的r实际上就是ddl，总是先处理快到“ddl”的区间。ps：结合实际生活来看，这的确是显然的。

r相等时，l按照从小到大排序，这是为了能让任务地起始时间有可能更早。

3. 模板

struct task {  // 一个任务
    int l, r, idx;
    task(int l, int r, int idx) : l(l), r(r), idx(idx) {}
    bool operator < (const task& rhs) const {
        return r < rhs.r || r == rhs.r && l < rhs.l;
    }
};
vector<task> vec;
......
fill(vis, vis + n + 1, 0);  // 用来标记某个时间是否被占用
sort(vec.begin(), vec.end());  // 按照 (r, l) 排序
for(const auto& p : vec) {
    int j = p.l;
    while(j <= p.r && vis[j]) j ++;  // 找第一个没被占用地时间点执行任务
    if(j == p.r + 1) return 0;
    ans[p.idx] = j, vis[j] = 1;  // 用ans记录任务p的执行时间
}
......

4. 例题

Uva 11134：https://blog.nowcoder.net/n/db0fa9391c414281a899097aeb67c0c8

五、区间限制问题之用时不等

1. 定义

有若干个工作，只能串行进行，已知每个工作的用时need[i]和截止期限ddl[i]，问最多能完成多少个工作？

2. 解析

这个是超典型的工作安排贪心问题。

一个比较简单的版本是给出工作的确切开始时间和结束时间，这种问题就是典型的区间限制问题，我们按照ddl排序，然后先完成ddl早的任务即可。

但是在这道题中，任务的开始时间是可以任意决定的（只要结束时不超过ddl期限），因此我们还应该结合考虑另一种贪心：即让短的任务优先。

也就是说，对于一个给定的时间点之前，我们需要先执行短的任务，这样才能让任务完成数量最大化。这里 需要用一个优先队列来存放到当前时间点为止，所有已经选择的任务 。用这个优先队列的目的是为了能获得已经选择的任务中用时最长的那一个，这样就能在当发现一个任务由于超时无法选择时可以有尝试替换的机会（即从之前选择的任务中挑一个用时长的取消掉，从而使得当前任务不会超时）。

贪心策略：按r从小到大进行排序，每次尽量早地执行任务。当碰到一个任务超时，尝试从之前选择的任务中挑一个用时长的取消掉，从而使得当前任务不会超时。

3. 模板

struct task {
    int need, ddl;
    task(int need, int ddl) : need(need), ddl(ddl) {}
    bool operator < (const task& rhs) const {
        return ddl < rhs.ddl;
    }
};

......
sort(vec.begin(), vec.end());

priority_queue<int> que;
int cur = 0;  // 当前时间点
for(const task& t : vec) {  // 总体上还是优先考虑ddl早的任务
    if(cur + t.need <= t.ddl) {  // 不超时
        cur += t.need;
        que.push(t.need);
    }
    else if(!que.empty() && que.top() > t.need) {  // 反正都会有一个任务不能完成，不如留下用时短的任务（当前任务）
        cur += t.need - que.top();                 // 即用这个ddl更晚的但用时更短的task替换一个ddl早一些但是用时长的task
        que.pop();                                 // 由于当前任务的ddl更晚，用时也更短，因此替换后必然不会超时
        que.push(t.need);
    }
}
cout << que.size() << endl;
......