题目描述

乐总有N个 (1 <= N <= 25,000)工人和一个谷仓，他希望他的工人可以帮助他清理谷仓，他将一天的时间分成了T (1 <= T <= 1,000,000)段，他手下的工人每天只在一定时间段才会工作，但乐总希望每个时间段都有工人在帮他打扫谷仓。

你的任务就是帮助小乐子分配这些工人，使一天的时间段中都有工人在工作，并且使用尽量少的工人(多一个工人就多一份钱呐！)

输入第一行 N,T 接下来每一行是每个工人的工作时间段

输出最少工人数量
如果无法达到要求，每个时间段都有工人，则输出-1

样例

3 10
1 7
3 6
6 10


2

算法1

(暴力枚举) $O(n^2)$

就是提高我的代码能力、

时间复杂度

参考文献

C++ 代码

#include <stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
//贪心
//我现在最大的问题是：如何把他们拼接起来呢？ 
/*
思路：贪心--->排序.
了解了cmp的排序机制。 根据真假来判断是否换位置。
首先，如果你的最小c[i].x!=1 那么直接输出-1即可。
如果是1，给个box标志代表我目前的最大区间。在这个最大区间范围内，（因为只要从c[i].x在这个最大区间内，
我们就不需要知道那个人是谁）找到能够使我最大区间最大的数。【end=Max(end,c[i].y);】
当超出我们目前的最大区间范围后，我们要记录这个时候的位置。【我用了index来表示】
判断一下如果我们确实找到了比我们当时的box要大，那么就人数+1，然后box=end+1（因为3~4 4~5 也是可以的）
如果之后的end没有大于box说明，你的范围没有变大，不能满足我们的时间t。所以flag=-1
或者如果 c[i].x直接比box+1要大说明他们中间肯定有间隔，所以也是flag=-1
大概的思路是这样吧。
*/
int t,n;
struct men
{
    int x;
    int y;
    int rank;
}c[3000000];//3000000
int cmp(struct men a,struct men b)
{
    if(a.x==b.x)
    {
        return a.y>b.y;
    }
    return a.x<b.x;
}
int Max(int a,int b)
{
    if(a>b) return a;
    return b;
}
int main()
{
    int i,j;
    int sum=0,ans=0,maxn=0,flag=1;
    while (~scanf("%d %d", &n,&t))
    {
        ans=1;
        for(i=0;i<n;i++)
        {
            scanf("%d %d",&c[i].x,&c[i].y);
        }
        sort(c,c+n,cmp);
        if(c[0].x!=1)
        {
            flag=0;
        }
        else
        {
            int index=1,box,end=c[0].y;
            while(end<t)
            {
                box=end+1;
                for(i=index;i<n;i++)
                {
                    if(c[i].x<=box){end=Max(end,c[i].y);}else {index=i;break;}
                }
                if(box>end)
                {
                    flag=0;
                    break;
                }
                else
                {
                    ans++;
                }

            }

        }
        if(flag)
        {
            printf("%d\n",ans);
        }
        else
        {
            puts("-1");
        }
        memset(c,0,sizeof(c));
        flag=1;

    }
    return 0;
}



/*
3 10
1 7
1 8
6 10

3 10
1 7
1 8
6 9

4 11
1 7
2 9
3 10
4 11

4 11
1 7
2 9
3 10
10 11

4 11
1 7
2 9
3 9
10 11
*/

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla