itdef

題目大意是 給出 N個區間 ，詢問最小需要選擇幾個區間能覆蓋 1~T的全部區間
第一行輸入 N和 T
后面N行 每行2個數字 表示區間的起點和終點
要求輸出一行 選擇的最小區間個數 若無法覆蓋全部區間 則輸出-1

Sample Input
3 10
1 7
3 6
6 10
Sample Output
2

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

const int N = 1000010;

/*
Sample Input

3 10
1 7
3 6
6 10
Sample Output

2
*/
int n;
struct Range
{
    int l, r;
    bool operator< (const Range& W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st, ed;
    scanf("%d%d", &n, &ed);
    st = 1;
    for (int i = 0; i < n; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i].l = l; range[i].r = r;
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i++)
    {
        int j = i, r = -2e9;
        //所有區間起點在當前點前的  取終點最遠的那個區間
        while (j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j++;
        }
        //如果所有區間都在當前點之前  那就無法覆蓋了 返回-1 跳出
        if (r < st)
        {
            res = -1;
            break;
        }
        //選擇區間個數加1
        res++;
        //選擇后的所有區間已經覆蓋到終點或者終點之后  那就得到了答案了
        if (r >= ed)
        {
            success = true;
            break;
        }
        //更新當前點 繼續下一輪尋找可覆蓋的區間
        st = r + 1;
        i = j - 1;
    }

    if (!success) res = -1;
    printf("%d\n", res);

    return 0;
}