HDU2037 贪心模板题

题目链接今年暑假不AC、

思想：主要用到贪心算法，从最局部最佳看整体最佳

一个尽快终止的活动可以容纳更多的后续活动。

1. 先把活动按结束时间的前后进行排序
2. 选择第一个结束的活动，删除与它时间相冲突的活动
3. 重复步骤2，直到结束

直接上代码吧

#include<bits/stdc++.h> //懒人万用头文件
using namespace std;
const int maxn = 1e5 + 10;
struct node{  //结构体存储开始和结束时间
    int start, end;
} record[maxn]; 
bool cmp(node& a,node& b) //sort函数递增排序
{
    return a.end < b.end;
}
int main()
{
    int n,i,cnt,temp;
    while(~scanf("%d",&n)&&n) 
    {
        for (i = 0; i < n; i++)
            cin >> record[i].start >> record[i].end; //输入开始与结束时间
        sort(record, record + n, cmp); //排序
        for (i = 1, cnt = 1, temp = record[0].end; i < n; i++)
        {
            if(record[i].start>=temp)  //后一个起始时间大于等于终止时间
            {
                cnt++;
                temp = record[i].end;
            }
        }
        cout << cnt << endl; //输出结果
    }
    return 0;
}