样例输入
4 10
1 3
2 4
5 7
9 10
样例输出
3
下面看一下一个贪心算法的典型例题 活动选择问题
有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
考虑使用贪心算法的解法。为了方便，我们用不同颜色的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝色的线条表示我们已经选择的活动；红色的线条表示我们没有选择的活动。
如果我们每次都选择开始时间最早的活动，不能得到最优解：
如果我们每次都选择持续时间最短的活动，不能得到最优解：
可以用数学归纳法证明，我们的贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。
通过代码如下：
#include<iostream>#include<algorithm>using namespace std;struct aa{int start ;int end ;};bool cmp(aa x,aa y){return x.end<=y.end;}void greedychoose(int n,int m,aa a[]){int s=1,i=1;for( int j=2;j<=n;j++ ){if(a[j].start>=a[i].end&&a[j].end<=m){i=j;s++;}}cout << s << endl ;}int main(){int n,m,i=1;cin >> n ;cin >> m ;aa time[n+5] ;while(i<=n){cin >> time[i].start >> time[i].end ;i++;}sort(time+1,time+n,cmp);//验证排序是否完成/*for(int j=1;j<=n;j++){cout << time[j].start << " " << time[j].end << endl ;}*/greedychoose(n,m,time);}
