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;
}