POJ - 2376 Cleaning Shifts
贪心做法：对左端点排个序，判断每个区间的右端点是否覆盖下一个区间的右端点，然后替换右端点变量，最后输出需要区间数量即可。
#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;typedef pair<int,int>PII;
const int N = 25010;PII section[N];
int n,m;int main()
{
cin>>n>>m;for(int i=0;i<n;i++) cin>>section[i].x>>section[i].y;sort(section,section+n);int res=0,right=1;for(int i=0;i<n,right<=m;){
int pos=0;while(i<n&§ion[i].x<=right){
if(section[i].y>=right)pos=max(pos,section[i].y);i++;}if(!pos) break;res++;right=pos+1; }if(right<=m) cout<<"-1"<<endl;else cout<<res<<endl; return 0;
}
数据结构优化DP做法
#include<iostream>
#include<algorithm>
using namespace std;const int N = 25010, M = 1000010, INF = 1e8;int n,m,e;
struct Range{
int l,r;
}range[N];struct Node{
int l,r,v;
}tr[M*4];bool cmp(Range A,Range B){
return A.r<B.r;}void pushup(int u)
{
tr[u].v=min(tr[u<<1].v,tr[u<<1|1].v);
} void build(int u,int l,int r)
{
tr[u]={
l,r,INF};if(l==r) return;else{
int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);}
}void update(int u,int k,int v)
{
if(tr[u].l==tr[u].r){
tr[u].v=min(tr[u].v,v);return ;}else{
int mid=tr[u].l+tr[u].r>>1; if(k<=mid) update(u<<1,k,v);else update(u<<1|1,k,v);pushup(u);}
}int query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r) return tr[u].v;else{
int mid=tr[u].l+tr[u].r>>1;int res=INF;if(l<=mid) res=query(u<<1,l,r);if(r>mid) res=min(res,query(u<<1|1,l,r));return res;}
}int main()
{
cin>>n>>m;build(1,0,m);update(1,0,0); for(int i=0;i<n;i++) cin>>range[i].l>>range[i].r;sort(range,range+n,cmp);for(int i=0;i<n;i++){
int l=range[i].l,r=range[i].r;int v=query(1,l-1,r-1)+1;update(1,r,v);}int res=query(1,m,m);if(res==INF) res=-1;cout<<res<<endl;return 0;
}