有若干個(gè)活動(dòng)，第i個(gè)開始時(shí)間和結(jié)束時(shí)間是[Si,fi)，同一個(gè)教室安排的活動(dòng)之間不能交疊，求要安排所有活動(dòng)，最少需要幾個(gè)室？?

輸入第一行一個(gè)正整數(shù)n (n <= 10000)代表活動(dòng)的個(gè)數(shù)。 第二行到第(n + 1)行包含n個(gè)開始時(shí)間和結(jié)束時(shí)間。 開始時(shí)間嚴(yán)格小于結(jié)束時(shí)間，并且時(shí)間都是非負(fù)整數(shù)，小于1000000000輸出一行包含一個(gè)整數(shù)表示最少教室的個(gè)數(shù)。輸入示例3 1 2 3 4 2 9輸出示例2

有若干個(gè)活動(dòng)，第i個(gè)開始時(shí)間和結(jié)束時(shí)間是[Si,fi)，活動(dòng)之間不能交疊，要把活動(dòng)都安排完，至少需要幾個(gè)教室？
分析：能否按照之一問題的解法，每個(gè)教室安排盡可能多的活動(dòng)，即按結(jié)束時(shí)間排序，再貪心選擇不沖突的活動(dòng)，安排一個(gè)教室之后，剩余的活動(dòng)再分配一個(gè)教室，繼續(xù)貪心選擇……

反例： A：[1,2) ?B：[1,4) C：[5,6) D：[3，7)已經(jīng)按結(jié)束時(shí)間排好順序，我們會(huì)選擇
教室1： A C
教室2: ?B
教室3: ?D
需要3個(gè)教室

但是如果換一種安排方法，我們可以安排AD在一個(gè)教室，而BC在另外一個(gè)教室，兩個(gè)教室就夠了。所以之前的貪心策略解決不了這個(gè)問題。
怎么辦？之前的策略是用一個(gè)教室找所有它能安排下的活動(dòng)，即用教室找活動(dòng)，我們能不能用活動(dòng)找教室呢？
策略： 按照開始時(shí)間排序優(yōu)先安排活動(dòng)，如果沖突，則加一個(gè)教室。
簡單地理解一下，策略是這樣，我們把活動(dòng)按照開始時(shí)間有小到大的順序排序。假設(shè)目前已經(jīng)分配了k個(gè)教室（顯然k初始等于0），對(duì)于當(dāng)前這個(gè)活動(dòng)，
（1） 如果它能安排在k個(gè)教室里的某一個(gè)，則把它安排在其中的任何一個(gè)教室里，k不變。
（2） 否則它和每個(gè)教室里的活動(dòng)都沖突，則增加一個(gè)教室，安排這個(gè)活動(dòng)。
這個(gè)策略是最優(yōu)么？
我們想像一下k增加1的過程： 因?yàn)槲覀兪前凑臻_始時(shí)間排序的，意味著當(dāng)前考慮的這個(gè)活動(dòng)開始的時(shí)候，k個(gè)教室里都有活動(dòng)沒結(jié)束（因?yàn)槿绻幸粋€(gè)教室的活動(dòng)結(jié)束了，我們就可以安排這個(gè)活動(dòng)進(jìn)入那個(gè)教室而不沖突，從而不用增加k)。這就意味著在這個(gè)活動(dòng)開始的時(shí)間點(diǎn)，算上目前考慮的這個(gè)活動(dòng)，有(k + 1)個(gè)活動(dòng)正在進(jìn)行，同一時(shí)刻有(k + 1)個(gè)活動(dòng)在進(jìn)行，無論我們?nèi)绾伟才沤淌?#xff0c;都至少需要(k + 1)個(gè)教室。因?yàn)槊總€(gè)教室里不能同時(shí)進(jìn)行兩個(gè)活動(dòng)。而我們的策略恰好需要(k + 1)個(gè)教室，所以是最優(yōu)的。
這個(gè)策略也告訴我們，如果從時(shí)間軸上“宏觀”考慮這個(gè)問題?？紤]每個(gè)時(shí)間點(diǎn)同時(shí)進(jìn)行的活動(dòng)個(gè)數(shù)，作為這個(gè)時(shí)間點(diǎn)的厚度（把活動(dòng)開始和結(jié)束時(shí)間想像成線段，那么每個(gè)時(shí)間點(diǎn)有多少條線段覆蓋它，可以簡單理解為“厚度”），我們至少需要最大厚度那么多個(gè)教室——因?yàn)槟菚r(shí)恰好有最大厚度那么多個(gè)活動(dòng)同時(shí)進(jìn)行，而我們這個(gè)貪心策略恰好給了我們一個(gè)用最大厚度那么多個(gè)教室安排全部活動(dòng)的一個(gè)方案。
如果只需要教室的個(gè)數(shù)，我們可以把所有開始時(shí)間和結(jié)束時(shí)間排序，遇到開始時(shí)間就把厚度加1，遇到結(jié)束時(shí)間就把厚度減1，顯然最初始和最后結(jié)束時(shí)的厚度是0，在一系列厚度變化的過程中，峰值（最大值）就是最多同時(shí)進(jìn)行的活動(dòng)數(shù)，也是我們至少需要的教室數(shù)。

方法一：就是51Nod里面講解的方法（上面的綠色部分），不需要使用結(jié)構(gòu)體

AC代碼：

#include<bits/stdc++.h> #define x 10010 using namespace std; int main() {int s[x],e[x];int n,i,k;scanf("%d",&n);for(i=0;i<n;i++) scanf("%d%d",&s[i],&e[i]);sort(s,s+n);sort(e,e+n);int sum=0;for(i=0,k=0;i<n;i++){if(s[i]<e[k]) sum++;else k++;}printf("%d\n",sum);return 0; }

方法二：使用結(jié)構(gòu)體（這種方法思路和方法一基本上一樣，但是時(shí)間復(fù)雜度大了好多）

//還有別的復(fù)雜度小的方法，但是水平有限，百度到的方法不（kan）會(huì)（bu）用（dong）

AC代碼：

#include<bits/stdc++.h> #define x 10100 using namespace std; struct wzy{int start,end; }p[x]; int cmp(wzy u,wzy v)//對(duì)時(shí)間進(jìn)行排序， {if(u.start!=v.start) return u.start<v.start;//開始時(shí)間不同，把先開始的放前面 else return u.end<v.end;//開始時(shí)間相同，把先結(jié)束的放前面 } int main() {int n,i,j,k,sum;scanf("%d",&n);for(i=0;i<n;i++) scanf("%d%d",&p[i].start,&p[i].end);sort(p,p+n,cmp);for(sum=0,i=0;i<n;i++){k=0;for(j=i;j>=0;j--)//每次都要從i往前推一邊，找出來在第i組數(shù)據(jù)的時(shí)候需要幾個(gè)房間 { //這個(gè)思路和方法一大致相同，都是找結(jié)束時(shí)間與開始時(shí)間的關(guān)系。從j=i開始是因?yàn)闊o論怎樣都至少需要一個(gè)房間 if(p[j].end>p[i].start)k++;}sum=sum>k?sum:k;//取最大值 }printf("%d\n",sum);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Friends-A/p/9309057.html

總結(jié)

以上是生活随笔為你收集整理的51Nod：活动安排问题之二（贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。