P4807 浇水问题（提高）

解题思路

1. 读懂题目：一条直线上从 0 到 m 的地方都需要浇水。有 n 个灌溉设备，每个设备能浇一个区间 [左,右]。问最少开通几个设备能把 0 到 m 全部浇到，如果怎么开都不行就输出 -1。

2. 打个比方：就像用几根竹竿去够远处的东西，每根竹竿要"接得上"前一根已经够到的位置，而且每次都要选能伸得最远的那根，这样用的竹竿最少。

3. 第一步：把所有设备按左端点从小到大排序，左端点相同的就把右端点大的排前面。

4. 第二步：用一个变量 current 记录目前已经浇灌到的最右位置，一开始是 0。

5. 第三步：每次在"左端点 ≤ current"的设备里，找一个右端点最大的设备开通它，然后 current 更新为这个右端点，设备数加 1。

6. 第四步：重复第三步，直到 current ≥ m，说明 0 到 m 全部被浇到了。

7. 判断无解：如果某一步发现，所有"左端点 ≤ current"的设备里，右端点最大也不超过 current，说明没有任何设备能让浇灌范围变大，中间断开了，就输出 -1。

8. 为什么贪心正确：current 左边已经全部浇到，接下来只需要关心右端点最远的设备，它能把当前浇到的位置推得最远，剩下的范围就最小，需要的设备就最少。

9. 边界情况：有的设备左端点是负数（从 0 左边就开始浇），有的设备右端点超过 m（多浇一点没关系）；如果有一个设备覆盖了整段 [0,m]，答案就是 1。

参考代码

// P4807 浇水问题：区间覆盖贪心，每次在能接上的设备里选右端点最远的，最少设备覆盖全段
#include <iostream>
#include <algorithm>
using namespace std;

struct Device {
    long long left;    // 灌溉设备覆盖的左端点
    long long right;   // 灌溉设备覆盖的右端点
};

Device device[200005];   // 每个灌溉设备

// 按左端点从小到大排序，左端点相同的右端点大的排前面
bool cmp(const Device& a, const Device& b) {
    if (a.left != b.left) return a.left < b.left;
    return a.right > b.right;
}

int main() {
    long long m;   // 植被最右端
    int n;         // 设备个数
    cin >> m >> n;
    for (int i = 0; i < n; i++) cin >> device[i].left >> device[i].right;
    sort(device, device + n, cmp);
    long long current = 0;   // 目前已经浇灌到的右端点
    int idx = 0;             // 扫描设备的指针
    int cnt = 0;             // 开通的设备数量
    while (current < m) {
        long long far = current;   // 能接上当前覆盖段的设备里，最远能到哪
        while (idx < n && device[idx].left <= current) {
            if (device[idx].right > far) far = device[idx].right;
            idx++;
        }
        if (far <= current) {
            // 没有设备能接着往下浇了，说明无法灌溉全部植被
            cout << -1 << endl;
            return 0;
        }
        current = far;
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

复杂度分析

排序需要 O(n log n) 的时间，排序后用两个指针扫描一遍所有设备，是 O(n)。所以总时间复杂度是 O(n log n)，空间复杂度是 O(n)。