P1668 Cleaning Shifts S

题面

题目描述

一天有 $T(1\le T\le 10^6)$ 个时段。约翰正打算安排他的 $N(1\le N\le 2.5\times 10^4)$ 只奶牛来值班，打扫打扫牛棚卫生。每只奶牛都有自己的空闲时间段 $ [S_i,E_i](1\le S_i\le E_i\le T)$，只能把空闲的奶牛安排出来值班。而且，每个时间段必需有奶牛在值班。

那么，最少需要动用多少奶牛参与值班呢？如果没有办法安排出合理的方案，就输出 $-1$。

输入格式

第 $1$ 行：$N$，$T$。

第 $2$ 到 $N+1$ 行：$S_i$，$E_i$。

输出格式

一行，输出最少安排的奶牛数。

样例 #1

样例输入 #1

3 10
1 7
3 6
6 10

样例输出 #1

2

提示

$1\le T\le 10^6$，$N\le 2.5\times 10^4$，$1\le S_i\le E_i\le T$。

思路

一眼题。

之前做过同类型的题，比如说，P1803或者P4155，就是一个贪心的区间覆盖问题。

一般的做法是给区间的左端点或者右端点排序，然后进行贪心。

拿以右端点降序举例：

依次枚举右端点，直到找到第一个符合左端点小于等于当前点的区间，然后更新右端点和新的当前点，因为是整数的区间覆盖，所以新的当前点等于新右端点加一。

若某次枚举完了所有的区间也没有符合条件的区间，那么就不存在答案，直接退出大循环。

若新的右端点大于等于$t$，那么才可以说找到了答案。注意这里不是新的当前点，万一新的右端点等于$t-1$，那么就会 WA。

但是哦，以左端点升序代码跑起来会更快，因为在枚举左端点找最大右端点的时候，我们可以保证下次一定是从上次枚举到的位置接着枚举，因为当前点变大了，左端点的上界就大了，可以直接从上次没枚举完的地方接着枚举，这样最多才枚举$n$边遍，而枚举右端点可不一定，因为它们的左端点是无序的，不一定枚举到哪才能符合条件，因此每次都需要重新枚举，跑起来就会慢一些。

代码

左端点升序：

#include<bits/stdc++.h>
using namespace std;
const int N=3e4;
int n,t,ans,r,j;
inline int read()
{
	int x=0,y=1;//x是什么，y是正负 
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-') y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*y;
}
struct edge
{
    int l,r;
    bool operator<(const edge &a)const
    {
        return l<a.l;
    }
}e[N];
int main()
{
    // scanf("%d%d",&n,&t);
    n=read(),t=read();
    for(int i=1;i<=n;i++)
    {
        e[i].l=read();
        e[i].r=read();
        // scanf("%d%d",&e[i].l,&e[i].r);
    }
    sort(e+1,e+n+1);
    int now=1;
    while(j<=n)
    {
        while(j<=n&&e[j].l<=now)
        {
            r=max(r,e[j].r);
            j++;
        }
        if(r<now) break;
        ans++;
        if(r==t)
        {
            cout<<ans;
            return 0;
        }
        now=r+1;
    }
    cout<<-1;
    return 0;
}

右端点降序：

#include<bits/stdc++.h>
using namespace std;
const int N=3e4;
int n,t,ans,r;
struct edge
{
    int l,r;
    bool operator<(const edge &a)const
    {
        return r>a.r;
    }
}e[N];
int main()
{
    scanf("%d%d",&n,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&e[i].l,&e[i].r);
    }
    sort(e+1,e+n+1);
    int now=1;
    while(true)
    {
        for(int i=1;i<=n;i++)
        {
            if(e[i].l<=now)
            {
                r=e[i].r;
                break;
            }
        }
        if(r<now) break;
        ans++;
        now=r+1;
        if(r==t)
        {
            cout<<ans;
            return 0;
        }
        
    }
    cout<<-1;
    return 0;
}