选择不相交区间

题目：有一些活动计划的时间表，想尽可能的安排更多的活动，请问该如何安排。

分析：这道题是典型的贪心问题。按照活动结束点排序，贪心解决

#include <iostream> #include <algorithm> using namespace std; struct node { int s; int g; } game[10001]; bool cmp(node a,node b) { return a.g<b.g; } int main() { int cnt; cin>>cnt; while(cnt--) { int n,tail=-1,num=0; cin>>n; for(int i=0; i<n; i++) cin>>game[i].s>>game[i].g; sort(game,game+n,cmp); for(int i=0; i<n; i++) { if(tail<game[i].s) { num++; tail=game[i].g; } } cout<<num<<endl; } }