Cleaning Shifts(区间覆盖)

时间:2024-07-09 18:36:56
/*

题目:

给定一个时间T和N个时间区间,求最少需要多少个区间覆盖总区间[1,T],无法覆盖区域[1,T]时输出-1。

例如T=10,有3个区间[1,7],[3,6],[8,10],则最少需要两个区间来覆盖,选择区间1和区间3。

解题思路:

使用贪心法。首先将区间按开始时间从小到大排序,开始时间相等按结束时间从小到大排序。

1 如果第一个区间不是从1开始,则无法覆盖,输出-1。

2 令当前覆盖到的时间time为开始时间为1的区间中结束时间的最大值。

3 从开始时间不为1的区间开始循环遍历。

4 选择合法区间中结束时间值最大的那个区间,合并到[1,time],合并后time为选择的区间的结束时间。所谓合法区间是指区间的起始时间start<=time+1,这样才能和区间[1,time]合并。如果没有找到合法区间或者找到的区间结束时间比time小,则无法覆盖,结束循环。

5 循环结束后,根据time是否大于等于T,输出结果。

*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct qujian
{
    int left;
    int right;
};
bool comp(qujian a,qujian b)
{
    if(a.left==b.left)return a.right<b.right;
    return a.left<b.left;
}
int main()
{
    int N,End;
    scanf("%d%d",&N,&End);
    struct qujian q[N+1];
    for(int i=1; i<=N; i++)
        scanf("%d%d",&q[i].left,&q[i].right);
    sort(q+1,q+N+1,comp);
    if(q[1].left>1)printf("-1\n");//肯定覆盖不了
    else
    {
        int temp=q[1].right,max=q[1].right;
        int count=1;
        int i=1;
        while(max<End)
        {
            if(q[i].left>max+1)i++;//此判断条件是为了防止与下面的i++重复,否则就会加两次了,
            if(i>N)break;//如果检索到结尾就结束
            // cout<<"max="<<max<<endl;
            if(max>=End) break;//即已经找到,可以覆盖了
            count++;//找到的区间个数
            while(q[i].left<=max+1)//[1,3] [4,6]视为连续的
            {
                if(temp<q[i].right)
                    temp=q[i].right;//满足条件下找到结尾最大的
                if(temp>=End)//已经覆盖,可以结束
                    break;
                i++;//依次向后寻找
                if(i>N)break;
            }
             max=temp;//记录最大的结尾
        }
        if(temp<End)printf("-1\n");//找完后仍不能覆盖
        else
            printf("%d\n",count);
    }
    return 0;
}
/*
4 10
3 10
1 2
4 10
10 11
*/
/*
3 10
1 7
3 6
6 10
*/
/*
4 10
1 10
3 5
4 8
6 10
*/