一：題目

假定一個有n個活動(activity)的集合S={a
1
?
,a
2
?
,…,a
n
?
}，這些活動使用同一個資源（例如同一個階梯教室），而這個資源在某個時刻只能供一個活動使用。每個活動a
i
?
都有一個開始時間s
i
?
和一個結束時間f
i
?
，其中0<=s
i
?
<f
i
?
<=32767。如果被選中，任務a
i
?
發生在半開時間區間[s
i
?
,f
i
?
)期間。如果兩個活動a
i
?
和a
j
?
滿足[s
i
?
,f
i
?
)和[s
j
?
,f
j
?
)不重疊，則稱它們是兼容的。也就說，若s
i
?

=f
j
?
或s
j
?
=f
i
?
，則a
i
?
和a
j
?
是兼容的。在活動選擇問題中，我們希望選出一個最大兼容活動集。

輸入格式:
第一行一個整數n(n≤1000)；

接下來的n行，每行兩個整數，第一個s
i
?
，第二個是f
i
?
(0<=s
i
?
<f
i
?
<=32767)。

輸出格式:
輸出最多能安排的活動個數。

輸入樣例:
11

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

結尾無空行
輸出樣例:

4

樣例解釋:
安排的4個活動為1 4, 5 7, 8 11和12 14。

二：分析題意+思路

1：分析

這個題就是讓我們求解無重疊區間的個數，是道經典的貪心算法題

2：思路

：1.這個題類似無重疊區間 就是最后求出的區間為互不重合的區間（不包括邊界）
2.那么我們在處理數據的時候是將 每兩個數存在一起，再用一個大的容器將其存起來
3.處理數據 我們按每組數據的結束時間 升序處理，
4.緊接著求出第一個區間右邊界，跟下一組的左邊界進行比較,如果小于等于其左邊界
那么說明區間不覆蓋了，我們就需要更新右邊界 我們統計其個數

三：處理數據

寶這道題在處理 數據的時候 你可以采用 結構題體數組來儲存數據，目的是可以重寫sort方法，讓每組數據的到達時間可以升序排序；但貼心杰用的vector的嵌套使用，因為我鐘愛 vector呀！講重點：我們處理數據的時候一定要想好你寫碼中會用到啥，比如這個題中需要將讓每組數據的到達時間可以升序排序，所以我們采用結構體數組或者是 vector嵌套使用！！！

四：上碼

/**思路：1.這個題類似無重疊區間 就是最后求出的區間為互不重合的區間（不包括邊界）2.那么我們在處理數據的時候是將 每兩個數存在一起，再用一個大的容器將其存起來3.處理數據 我們按每組數據的結束時間 升序處理，4.緊接著求出第一個區間右邊界，跟下一組的左邊界進行比較,如果小于等于其左邊界那么說明區間不覆蓋了，我們就需要更新右邊界 我們統計其個數*/#include<bits/stdc++.h> using namespace std;//處理每組的數據讓其第二個值大于前一個值 static bool cmp(const vector<int>& a, const vector<int>& b){return a[1] < b[1]; } int main(){int N;int count = 1;//表示取出的第一個區間第一組數據 vector<vector<int> >v;//注意這里的空格 一定要有 這是大容器存每組的數據 vector<int>v1;//存一組數據 cin >> N;for(int i = 0; i < N; i++){for(int j = 0; j < 2; j++){int temp;cin >> temp;v1.push_back(temp);} v.push_back(v1);v1.clear();//清空一次v1容器 為了存下一組數據 } //驗證輸出的數據 // for(int i = 0; i < N; i++){ // // for(int j = 0; j < 2; j++){ // cout << v[i][j] << " "; // } // cout << endl; // } sort(v.begin(),v.end(),cmp); int num = v[0][1];//第一組數據的右邊界for(int i = 1; i < N; i++){if(num <= v[i][0]){//如果后一個數的左邊界 大于等于其右邊界的話 num = v[i][1];//這時候就可以更新右邊界了，因為 已經確立了一組不相交的區間了count++; }} cout << count; }

五：擴展延申

做完這道題其實和leedcode有道題類似 可以給趕緊拿來練練手

leedcode：直接搜題號 435

435的題解

六:知識速遞（如果對vector的嵌套不熟悉的寶寶 可以學習下方的模板）

自己拿碼運行運行 在理解敲幾遍 ，這個知識就是你的了寶

#include<bits/stdc++.h> using namespace std;//處理每組的數據讓其第二個值大于前一個值 static bool cmp(const vector<int>& a, const vector<int>& b){return a[1] < b[1]; } int main(){vector<vector<int> >v; //得留出空格 vector<int>v1; //添加的時候需要一個 vector<int>v1; 來表示第一行的數據 for(int i = 0; i < 3; i++){for(int j = 0; j < 2;j++){v1.push_back(j);}v.push_back(v1);v1.clear(); }//訪問嵌套vector for(int i = 0; i < 3; i++){for(int j = 0; j < 2;j++){ cout << v[i][j] << ' '; }cout << endl;}}

最后還得再嘮叨一句 記得加油 寶寶！！！！！！！！！！！！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的7-1 活动选择问题 (25 分)(思路+详解+扩展)宝 今天你AC了吗！！！的全部內容，希望文章能夠幫你解決所遇到的問題。

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