題目鏈接： http://acm.tju.edu.cn/toj/showp.php?pid=2867

題目大意：給定一系列活動的開始時間和結(jié)束時間，問最多能參加的活動數(shù)目

思路：// 本題屬于最大區(qū)間調(diào)度問題，即數(shù)軸上有n個區(qū)間，選出最多的區(qū)間，使這些區(qū)間互相不重疊。算法：按右端點坐標(biāo)排序，然后依次按后者的開始時間是否大于前者的結(jié)束時間（注意更新前者的下標(biāo)）選擇所有能選的區(qū)間。

代碼：

//?? 本題屬于最大區(qū)間調(diào)度問題，即數(shù)軸上有n個區(qū)間，選出最多的區(qū)間，使這些區(qū)間互相不重疊。
//??? 算法：按右端點坐標(biāo)排序，然后依次按后者的開始時間是否大于前者的結(jié)束時間（注意更新前者的下標(biāo)）選擇所有能選的區(qū)間。
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
int s,e;
}activity[10000];
bool cmp(node a,node b)
{
?return a.e<b.e;? //按結(jié)束時間排序
}

int main()
{
? int n,d,st,i,ct,m;
? while(cin>>n&&n)
? {
??? ct = 1;????????? //最多能參加的活動數(shù)? 初始化為1！！
?for(i=0;i<n;i++)
?{
??cin>>st>>d;
??activity[i].s = st;
??activity[i].e = st+d;
?}
?sort(activity,activity+n,cmp);
?m=0;???????????
?for(i=1;i<n;i++)
?{
??if(activity[i].s>=activity[m].e)
??{
??? ct++;?? //如果后者的開始時間大于前者的結(jié)束時間，表明沒有重合，能參加的活動數(shù)目加1
??? m=i;??? //后者和前者比，記著更新
??}
?}
?cout<< ct<<endl;
? }
? return 0;
}

?

?

toj2867 Picking Problem