农民约翰正在指挥他的N头牛进行清理工作。
他将一天划分为了T个班次(1~T)。
每头牛都只能在一天中的某一个时间段内进行不间断的工作。
你需要帮助约翰排列出一个合理的奶牛的清理班次,使得每个班次都有奶牛在进行清理,而且动用的奶牛数量可以尽可能的少。
输入格式
第1行:两个空格隔开的整数N和T。
第2…N+1行:第i+1行包含两个整数,分别表示第i头牛可以进行工作的开始时间和结束时间。
输出格式
输出一个整数,表示在每个班次都有奶牛清理的情况下,所需的奶牛最小数量。
如果无法做到每个班次都有奶牛清理,则输出-1。
数据范围
1≤N≤25000,
1≤T≤106
输入样例:
3 10
1 7
3 6
6 10
输出样例:
2
解题报告:这题其实就是区间覆盖的问题,问选择多少条区间可以覆盖整个区间,然后也可以dp做,dp数组定义为前i小时合法(包括第i小时),我们将区间按照右端点排序,因为只有将右端点排序才没有后效性,比如1 5
3 4 如果1 5 先来 那么3 4 的信息就更新不到5了,转移方程=f[r] = min(f[r],f[l-1~r-1]+1),看了好久都不大懂,后来才发现,区间是可以相交的 r不一定只被l-1所更新,只要在l-1到 r-1的范围都可以使用l~r这条线段。接下来就是复杂度的分析 复杂度O(n^2),会超时,那么就线段树优化,维护区间最小值即可。
代码:
#include<iostream>
#include<cstring>
using namespace std;
const int N=1000010;
const int INF=1e9;
int p = 1;
struct node{
int l;
int r;
int minv;
}tr[N*4];
int n,m;
void build(int u,int l,int r)
{
tr[u]={
l,r,INF};
if(l==r)
return ;
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void mdf(int u,int x,int d)
{
if(tr[u].l==x && tr[u].r==x)
{
tr[u].minv=d;
return;
}
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid ) mdf(u<<1,x,d);
else mdf(u<<1|1,x,d);
tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);
}
int query(int u,int l,int r)
{
if(tr[u].l>=l && tr[u].r<=r)
return tr[u].minv;
int mid=tr[u].l+tr[u].r>>1;
int res=INF;
if(l<=mid) res=min(res,query(u<<1,l,r));
if(r>mid) res=min(res,query(u<<1|1,l,r));
return res;
}
typedef pair<int,int> pii;
pii q[N];
bool cmp(pii a,pii b)
{
if(a.second !=b.second)
return a.second < b.second;
return a.first < b.first;
}
int main()
{
cin >> n >> m;
for(int i=0;i<n;i++)
{
cin >> q[i].first >> q[i].second;
}
build(1,0,m);
mdf(1,0,0);
sort(q,q+n,cmp);
for(int i=0;i<n;i++)
{
int l=q[i].first;
int r=q[i].second;
int minv=min(query(1,l-1,r-1) + 1,query(1,r,r) );
mdf(1,r,minv);
}
cout << (query(1,m,m)==INF ? -1 : query(1,m,m))<<endl;
return 0;
return 0;
}