题目描述

给定N个闭区间[ai,bi]以及一个线段区间[s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出-1。

白话理解：

从给定的区间库中选择区间，去覆盖目标区间，找到所有方案中使用区间数最少的方案

联想生活，打扫教室的卫生，你有很多工具可以去使用，但是每个工具都有打扫范围，给你了个任务去某个区域的卫生，为了不频繁的更换工具打扫，你要想办法办法选出最少的工具数，去完成打扫任务

样例

输入样例：

1 5
3
-1 3
2 4
3 5

输出样例：

2

算法1

(贪心) $O(nlogn)$

思路

[st,ed] 目标覆盖区间 中为还未覆盖的区间

• 将区间按照左端点排序

• 枚举区间 ,找到能够覆盖待覆盖区间左端点的区间方案，且选择所有方案中区间的右端点最右的这一区间方案,假设其右端点为r

  • 如果该区间的右端点已经r >= ed 说明已经覆盖
  • 若 r < ed , 说明覆盖了一部分[st,r] 还剩下[r, ed]未覆盖 把st更新为r
  • 值得注意的是 r < st 这样无解

c ++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
vector<PII> segs;
int st, ed, n;

int overlap(vector<PII> &segs)
{
    int res = 0;
    bool success = false;
    sort(segs.begin(), segs.end());

    for(int i = 0; i < n; i++)
    {
        int j = i, r = -2e9; 

        while(j < n && segs[j].first <= st)  // segs[j] 而不是i
        {
            r = max(r, segs[j].second);
            j ++;
        }
        //  r 可覆盖的还未被覆盖的目标区间起点的区间 右端点 最右的位置
        if(r < st)
        {
            res = -1;  break;
        }
        //注意和后面if的先后顺序
        res ++; 
        if(r >= ed)
        {
            success = true; break;
        }

        // 更新未覆盖的区间的起点
        st = r;
        i = j - 1;

    }

    if(!success)  res = -1; // 这里别忘了
    return res;
}


int main()
{
    cin >> st >> ed >> n;

    for(int i = 0; i < n; i++)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    cout << overlap(segs) << endl;

    return  0 ;

}