每周一算法：区间覆盖

问题描述

给定$N$个闭区间$[a_i,b_i]$，以及一个线段区间$[s,t]$，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出$?1$。

输入格式

第一行包含两个整数$s$和$t$，表示给定线段区间的两个端点。

第二行包含整数$N$，表示给定区间数。

接下来$N$行，每行包含两个整数$a_i,b_i$，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需最少区间数。

如果无解，则输出$?1$。

数据范围

$1\le N\le 10^5$，$?10^9\le a_i\le b_i\le 10^9$，

$?10^9\le s\le t\le 10^9$

输入样例

1 5
3
-1 3
2 4
3 5

输出样例

2

算法思想

从测试样例分析，要覆盖线段区间$[1,5]$，只需要$2$个闭区间$[?1,3]$和$[3,5]$，如下图所示。

可以采用贪心的思想来解决这个问题：

• 首先将$N$个闭区间$[a_i,b_i]$按左端点排序
• 从前向后遍历每个区间
  • 在所有能覆盖线段区间$[s,t]$左端点$s$的区间中，选择右端点最大的区间$[a_j,b_j]$，其中$a_j\le s$，表示能够覆盖点$s$。
  • 然后将$s$更新成所有满足条件的区间中右端点的最大值
  • 重复上述过程，直到$s\ge t$，表示线段区间被完全覆盖

时间复杂度

• 将$n$个区间排序的时间复杂度为$O(nlogn)$
• 从前向后遍历每个区间，由于每个区间仅会处理$1$次，因此时间复杂度为$O(n)$

总的时间复杂度为$O(n+nlogn)$

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
PII st[N];
int main()
{
    int s, t, n, ans = 0, flag = 0;
    cin >> s >> t >> n;
    for(int i = 0; i < n; i ++) cin >> st[i].first >> st[i].second;
    //排序
    sort(st, st + n);
    for(int i = 0; i < n; i ++)
    {
    	//在所有能覆盖线段左端点s的区间中，选择右端点最大的区间
        int j = i, R = -1e9;
        while(j < n && st[j].first <= s) R = max(R, st[j ++].second);
        
        //无法覆盖左端点s
        if(R < s) break;
        
        ans ++; //需要的区间个数增加1
        
        s = R; //更新要覆盖的左端点
        if(s >= t) //覆盖完成
        {
            flag = 1;
            break;
        }
        
        i = j - 1; //继续从当前区间向后遍历
    }
    if(flag) cout << ans;
    else cout << -1;
    return 0;
}