原题链接

解题思路

  1. 将所有区间按左端点从小到大排序
  2. 从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择右端点最大的区间，然后将start更新为右端点的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int n, s, t, res;
vector<pair<int,int>> v;
#define MIN_INF -2e9
int main() {
    scanf("%d%d%d", &s, &t, &n);
    int r = MIN_INF, l = MIN_INF;
    for(int i = 0; i < n; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        v.push_back(make_pair(a, b));
    }
    sort(v.begin(), v.end());

    bool success = false;
    for(int i = 0; i < n; ++i) {
        int j = i, tmp_r = MIN_INF;
        while(j < n && v[j].first <= s) {
            tmp_r = max(tmp_r, v[j].second);
            j++;
        }
        if(tmp_r < s) {
            res = -1;
            break;
        }
        res++;
        if(tmp_r >= t) {
            success = true;
            break;
        }
        s = tmp_r;
        i = j - 1;
    }
    if(!success) printf("-1");
    else printf("%d", res);
    return 0;
}

不知道为什么，MIN_INF改成-1000000001就会有问题:cry:。