区间贪心问题总结

区间分组

这类问题指的是如何将n个互有交集的区间分成k组，使得这k组中每一组中所安排的任务不发生冲突，同时我们还希望让k尽可能的小。这种问题的解决方法是按照区间的左端点进行排序，然后遍历这个排序的区间，如果当前遍历到的区间可以加入某个以分配的组，我们就将其加入，否则的话就新开一个组来将其放入。

例题的话，则是畜栏预定, 其题目描述为有 N 头牛在畜栏中吃草，每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。给定 N 头牛和每头牛开始吃草的时间 A 以及结束吃草的时间 B，每头牛在 [A,B] 这一时间段内都会一直吃草。当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。求需要的最小畜栏数目和每头牛对应的畜栏方案。

代码如下，解题思路正如上面所说，不过有个细节是我们可以通过小根堆来维护当前所有组内最早的结束时间，而不是每个组都去遍历一遍。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ppii = pair<pair<int, int>, int>;
int n;
ppii cows[50001];
int id[50001];
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> cows[i].first.first >> cows[i].first.second;
        cows[i].second = i;
    }
    sort(cows, cows + n);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 0; i < n; ++i) {
        auto cow = cows[i];
        if(pq.empty() || pq.top().first >= cow.first.first) {
            id[cow.second] = pq.size();
            pq.push({cow.first.second, pq.size()});
        } else {
            auto top_element = pq.top();
            pq.pop();
            top_element.first = cow.first.second;
            id[cow.second] = top_element.second;
            pq.push(top_element);
        }
    }
    cout << pq.size() << endl;
    for(int i = 0; i < n; ++i) {
        cout << id[i] + 1 << endl;
    }
    return 0;
}

通过最小数量的点覆盖所有区间

题目模型如下：我们有若干组区间，并且还可以放置若干组点，我们希望用尽可能少的点来覆盖所有的区间，应该如何做到。
解法:

1. 将所有区间按右端点从小到大排序
2. 依次考虑每个区间：
   • 如果当前区间包含最后一个选择的点，则直接跳过；
   • 如果当前区间不包含最后一个选择的点，则在当前区间的右端点的位置选一个新的点；

例题：雷达游戏

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
};
int n, d;
Point islands[1001];
vector<pair<double, double>> seq;
const double eps = 1e-6;
void solve() {
    
    for(int i = 0; i < n; ++i) {
        auto island = islands[i];
        if(island.y > d) {
            cout << -1 << endl;
            return;
        }
        double dis = sqrt(d * d - island.y * island.y);
        seq.emplace_back(make_pair(island.x - dis, island.x + dis));
    }
    sort(std::begin(seq), std::end(seq), [&](const pair<double, double>& a, const pair<double, double>& b) {
        return a.second < b.second;
    });
    int ans = 0;
    double last_pos = INT_MIN;
    for(size_t i = 0; i < n; ++i) {
        if(seq[i].first > last_pos + eps) {
            last_pos = seq[i].second;
            ++ans;
        }
    }
    cout << ans << endl;
}

int main() {
    cin >> n >> d;
    for(size_t i = 0; i < n; ++i) {
        cin >> islands[i].x >> islands[i].y;
    }
    solve();
    return 0;
}