題目連結今年暑假不AC、
思想:主要用到貪心算法,從最局部最佳看整體最佳
一個盡快終止的活動可以容納更多的後續活動。
- 先把活動按結束時間的前後進行排序
- 選擇第一個結束的活動,删除與它時間相沖突的活動
- 重複步驟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;
}