题目描述

题目大意是 给出 N个区间 ，询问最小需要选择几个区间能覆盖 1~T的全部区间
第一行输入 N和 T
后面N行 每行2个数字 表示区间的起点和终点
要求输出一行 选择的最小区间个数 若无法覆盖全部区间 则输出-1

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

算法1

贪心 将所有区间按照起点排序

选择能覆盖当前点且结束最迟的区间 然后更新当前点到选择的区间最迟的坐标 继续选择

本来以为是一个区间覆盖的模版题，结果wa了一下午，poj没有数据提,偏偏样例还能过

看了别人的题解才发现 1~5 6~10居然也算是覆盖了1~10全区间 这个没数据真看不出来
吐血 写了一下午 上了Y总的模板 将输入修改了下 每次选择区间更新起点 从st = r 修改为st = r+1
AC

C++ 代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

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++;
        }

        if (r < st)
        {
            res = -1;
            break;
        }

        res++;
        if (r >= ed)
        {
            success = true;
            break;
        }

        st = r+1;
        i = j - 1;
    }

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

    return 0;
}

我的视频题解空间