九度OJ 1463 招聘會
這個題目是典型的貪心問題。貪心策略如下：按照結束時間進行從小到大排序，從第一個開始遍歷排序後的招聘會一遍得出結果，每次設置一個temp進行記錄當前所在招聘會，下一個招聘會向後找到第一個不沖突的，然後修改temp，當然此時能參加的招聘會要+1。
貪心策略簡單證明：假設有兩個招聘會A和B，且A的結束時間要早於B的結束時間，那麼顯然我們選擇B的時候B的所有後續安排全部不會和A沖突，而選擇A的時候A的後續卻不一定滿足不與B沖突。一個直觀的理解就是越早完成的招聘會會給後續招聘會騰出更多時間。
貼代碼，注意題目描述有點瑕疵，輸入並不止一組。
#include
#include
using namespace std;
struct node{
int start;
int end;
};
bool cmp(node a,node b)
{
if(a.end<=b.end)
return true;
return false;
}
node act[10050];
int main()
{
int n,i;
while(cin>>n)
{
for(i=1;i<=n;i++)
cin>>act[i].start>>act[i].end;
sort(act+1,act+1+n,cmp);
int temp=1;
int sum=1;
for(i=2;i<=n;i++)
{
if(act[i].start>=act[temp].end)
{
temp=i;
sum=sum+1;
}
}
cout<
