問題描述
有一個需要使用每個資源的n個活動組成的集合S= {a1，a2，···，an },資源每次只能由一個活動使用。每個活動a都有一個開始時間和結束時間，且 0<= s < f < 。一旦被選擇后，活動a就占據半開時間區間[s,f]。如果[s,f]和[s,f]互不重疊，則稱兩個活動是兼容的。該問題就是要找出一個由互相兼容的活動組成的最大子集。

輸入

11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13

輸出
4

貪心算法的主要思想就是對問題求解時，總是做出在當前看來是最好的選擇，產生一個局部最優解。

　　在活動選擇問題中，每次的貪心解就是選擇Sij結束時間最早的活動，這樣就給后面的活動留下了目前看來最多的時間。假設活動已經按照結束時間遞增的順序進行排序，那么我們只需要遍歷一次所有活動就可以得到最大兼容活動子集了。

#include<iostream> #include<algorithm> using namespace std;struct s{int begin;int end; }; int sql(s &a, s &b){return a.end<b.end; }int main(){int n;cin>>n;s a[1001];for(int i=1;i<=n;++i){cin>>a[i].begin>>a[i].end;}int num=0,begin=0,sum=0;sort(a+1,a+n+1,sql);for(int i=1;i<=n;++i){if(a[i].begin>=begin){num++;//sum+=a[i].end-a[i].begin+1;begin=a[i].end;}} cout<<num<<endl;//cout<<sum<<endl;return 0; }

總結

以上是生活随笔為你收集整理的（贪心）活动选择的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。