题目描述

blablabla

样例

blablabla

参考链接：
https://blog.csdn.net/sinat_38816924/article/details/82934967

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=100005;

struct timetable
{
    int a;
    int b;
}time1[maxn];

bool comp(timetable &x,timetable &y)//多看两遍
{
    return (x.a<y.a);
}



int main()
{
    int i,j,n,count;
    int begin,end;
    cin>>begin>>end;
    cin>>n;//n个区间
    for(i=0;i<n;i++)
    {
        cin>>time1[i].a;
        cin>>time1[i].b;
    }

    sort(time1,time1+n,comp);//区间按照a从小到大排序

    count=0;
    int len=0,maxlen,tmp;
    int newbegin=begin;
    i=0;
    while(len<end-begin)
    {
        maxlen=0;
        for(i;i<n;i++)//找当前begin情况下最长
        {
            if(time1[i].a<=newbegin)
            {
                tmp=time1[i].b-newbegin;
                if(tmp>maxlen)
                {
                    maxlen=tmp;
                    j=i;
                }
            }
            else
                break;
        }

        if(maxlen==0)//说明断了，不存在连续覆盖
        {
            cout<<-1;
            return 0;
        }

        len+=maxlen;
        count++;
        newbegin=time1[j].b;

    }
    cout<<count<<endl;
}

java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static class Interval implements Comparable<Interval>{
        int a;
        int b;

        public Interval(int a, int b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public int compareTo(Interval y) {
            return this.a>y.a?1:-1;
        }
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int count=0;
        int begin=scanner.nextInt();
        int end=scanner.nextInt();
        int n=scanner.nextInt();
        Interval arr[]=new Interval[n];
        for (int i = 0; i < n; i++) {
            arr[i]=new Interval(scanner.nextInt(),scanner.nextInt());
        }
        Arrays.sort(arr);
        int len=0,maxlen,tmp;
        int newbegin=begin;
        int i=0;
        int j=0;
        while(len<end-begin)
        {
            maxlen=0;
            for(;i<n;i++)//找当前begin情况下最长
            {
                if(arr[i].a<=newbegin)
                {
                    tmp=arr[i].b-newbegin;
                    if(tmp>maxlen)
                    {
                        maxlen=tmp;
                        j=i;
                    }
                }
                else
                    break;
            }

            if(maxlen==0)//说明断了，不存在连续覆盖
            {
                count=-1;
                break;
            }

            len+=maxlen;
            count++;
            newbegin=arr[j].b;

        }
        System.out.println(count);
    }
}