附另一：此類問題選題總結：https://blog.csdn.net/qq_41289920/article/details/81001357

題干：

會場安排問題
時間限制：3000 ms | 內存限制：65535 KB
難度：4
描述
學校的小禮堂每天都會有許多活動，有時間這些活動的計劃時間會發生沖突，需要選擇出一些活動進行舉辦。小劉的工作就是安排學校小禮堂的活動，每個時間最多安排一個活動?，F在小劉有一些活動計劃的時間表，他想盡可能的安排更多的活動，請問他該如何安排。
輸入
第一行是一個整型數m(m<100)表示共有m組測試數據。
每組測試數據的第一行是一個整數n(1<n<10000)表示該測試數據共有n個活動。
隨后的n行，每行有兩個正整數Bi,Ei(0<=Bi,Ei<10000),分別表示第i個活動的起始與結束時間（Bi<=Ei)
輸出
對于每一組輸入，輸出最多能夠安排的活動數量。
每組的輸出占一行
樣例輸入
2
2
1 10
10 11
3
1 10
10 11
11 20
樣例輸出
1

2

提示注意：如果上一個活動在t時間結束，下一個活動最早應該在t+1時間開始

解題報告：

以下給出三種方法，，只有一種是正確的 。

? ? 1.按照start從小到大排同時end從小到大，然后0~n-1遍歷。

? ? 2.按照end從大到小排同時start從大到小排，然后0~n-1遍歷。

? ? 3.按照end從小到大排同時start從小到大排（其實start無所謂），然后0~n-1遍歷。

? ?不難看出，只有3是成立的。? ??

證明：首先1和2肯定是綁定的，即如果成立均成立，如果不立均不立。因為其實模擬一組樣例畫出圖來之后倒著看，1和2的方法是一模一樣的，或者說，在1中找到一組樣例否定掉這種方法，那么樣例倒過來之后也可以否定掉第二種方法。

所以下證方法1是錯誤的：

? ? 證明是錯誤的方法很簡單，找一個特例否定掉他：（下面給的是排完序后的）

????????? ? 1,5

????????? ? 6,100

????????? ? 7,9

????????? ? 11,13

????????? ? 15,16

顯然。

下證方法3是正確的：

************************************************************************************

經典的區間貪心問題。將每個區間按右端點進行排序，每次第一個區間一定要選，然后重新確定起點，再第一個一定要選。

證明如下：設前兩個區間為（a1, b1）, （a2, b2），且b1<b2(即已經按b排好序了)

（1）當b1<a2

這種情況區間1和區間2不沖突,這樣做一定是對的

（2）當第一個區間與其他區間起沖突了，而且第一個區間可能與很多區間同時起沖突了。但是所以這些起沖突的區間只能取一個。對于第一個區間要么取要么不取兩個情況 ? ? ?

1）如果最后答案里有這個區間，先取后取一個樣的，那么還不如第一下就取了

2）假設最后答案里沒有這個區間，我們能推出矛盾，那不就說明“最后答案里沒有這個區間“這個假設是錯的。因為剛開始起沖突的那些區間一定只能選一個，如果你選了其他，可是這個區間一定可以被第一個替換掉，所以最后答案里又會出現第一個區間。

（證明選自：https://blog.csdn.net/shiwaigaoren12345/article/details/50767381）

所以是正確的。

*************************************************************************************

下面給出三種方法的代碼：

方法1：

#include<iostream> #include<cstdio> #include<algorithm> using namespace std;struct Node {int s,e; } node[10000 + 5]; //貪心排序起點做不出來！需要排end！ bool cmp(const Node & a, const Node & b) {if(a.s!=b.s) return a.s<b.s;else return a.e<b.e; } int main() {int m,n;scanf("%d",&m);while(m--) {scanf("%d",&n);for(int i = 0; i<n; i++) {scanf("%d %d",&node[i].s,&node[i].e); }sort(node,node+n,cmp);int curs=node[0].s;int cure=node[0].e;int ans=1;int i = 1;while(i<n) {if(node[i].s==node[i-1].s) {curs=node[i].s;cure=min(cure,node[i].e);continue;}if(node[i].s>cure) {ans++;cur}}}return 0 ; }

沒有寫完，，，因為寫不動了，，，即 很早的發現了錯誤。。

方法2：

#include<iostream> #include<cstdio> #include<algorithm> using namespace std;struct Node {int s,e; } node[10000 + 5]; //貪心排序起點做不出來！需要排end！ 這樣做從大到小排 依然是錯的，因為和排start一樣了啊。。你倒著看看 ，畫個圖 bool cmp(const Node & a, const Node & b) {if(a.e!=b.e) return a.e>b.e;else return a.s>b.s; } int main() {int m,n; // freopen("in.txt","r",stdin);scanf("%d",&m);while(m--) {scanf("%d",&n);for(int i = 0; i<n; i++) {scanf("%d %d",&node[i].s,&node[i].e); }sort(node,node+n,cmp); // for(int i = 0; i<n; i++) { // printf("%d %d\n",node[i].s,node[i].e); // }int curs=node[0].s;int cure=node[0].e;int ans=1;int i = 1;while(i<n) {if(node[i].e==node[i-1].e) {cure=node[i].e;curs=max(curs,node[i].s);i++;continue;}if(node[i].e<curs) {ans++;cure=node[i].e;curs=node[i].s;i++;}else {i++;}}printf("%d\n",ans);}return 0 ; } 這種方法仔細分析會發現就是第一種方法。。

方法3：（ac代碼）

#include<iostream> #include<cstdio> #include<algorithm> using namespace std;struct Node {int s,e; } node[10000 + 5]; //貪心排序起點做不出來！需要排end！ 并且是小到大排 ！！ bool cmp(const Node & a, const Node & b) {if(a.e!=b.e) return a.e<b.e;else return a.s>b.s;//其實這句就沒用了 } int main() {int m,n; // freopen("in.txt","r",stdin);scanf("%d",&m);while(m--) {scanf("%d",&n);for(int i = 0; i<n; i++) {scanf("%d %d",&node[i].s,&node[i].e); }//養成輸入完接著就排序的好習慣，若是放在while前面，，對于本題那就錯了！！ sort(node,node+n,cmp);int curs=node[0].s;//其實curs全程沒用，可以刪掉。 int cure=node[0].e;int ans=1;int i = 1;while(i<n) {//如果是 if(node[i].e==node[i-1].e)就錯了、、、 //并且這個if可以刪掉、、if(node[i].e==cure) {cure=node[i].e;curs=max(curs,node[i].s);i++;continue;}if(node[i].s>cure) {ans++; cure=node[i].e;//思想的精華！！curs=node[i].s;//curs依舊是，，沒啥用、、、 i++;}else {i++;}}printf("%d\n",ans);}return 0 ; }

總結

1.上面這一步就看出 升序排end并且從0遞歸到n-1的妙處了！！

2.做題方法：先讀題并確定需要找出的是什么（即以什么變量為中心點）！

此題根據題意你需要找出的是，每一步的end都是最小的那個（最優解），所以對end排序。
因為你每確定出一個ans，都能保證此時的end是最小的！而start是否滿足，不用排序出來，而是if判斷一步就好了啊。所以這題關鍵不是start而是end！（最后一段的理解可以看一下上面我給的樣例）?
3.對于sort排序，一定要找清楚位置，不然很容易犯很低級的錯誤并且很難查出來

4.if判斷啊邏輯關系要找清楚，第一個if那里，就一直寫錯了，

????????????寫成了if(node[i].e==node[i-1].e)。所以這個if還不如不要，，，反正不影響程序、

5.送上 區間完全不覆蓋 模板。

核心語句：

/* for(i=0; i<n; i++){if(node[i].s>cure){ans++;cure=node[i].e;}} */
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的NYOJ-14 会场安排问题（经典贪心，区间完全不覆盖模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

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