轉(zhuǎn)載請注明原創(chuàng)：http://www.cnblogs.com/StartoverX/p/4608412.html

題目：

　　有一組活動，我們需要將它們安排到一些教室，任意活動都可以在任意教室進行。我們希望使用最少的教室完成所有活動。

　　設(shè)計一個高效的貪心算法求每個活動應(yīng)該在哪個教室進行。

?

分析：

　　本題是對書中活動選擇問題的一個擴展。在活動選擇問題中，我們要求的是一個最大兼容活動集，也就是在所有時間內(nèi)時間不重疊的最多的活動集合。

　　易知，這樣一個活動集，就是一個教室最多能夠舉辦的活動集。所以剩下的活動一定不能和該活動集內(nèi)的活動在同一個教室舉行。我們不斷對剩下的活動使用貪心算法，需要多少次貪心能夠選取完所有的活動，就最少需要幾個教室。

　　我們首先對所有活動按結(jié)束時間排序。遍歷所有活動，如果下一個活動開始時間比某教室中最后一個活動結(jié)束時間晚，則加入該教室。如果不能加入已使用的任何教室，則需要新開一個教室。

#include <iostream> #include <vector> #include <utility> #include <algorithm>using namespace std;typedef pair<int,int> Acti;//用起始時間和結(jié)束時間的pair表示一個活動。void party(vector<Acti>& acti_vec) { sort(acti_vec.begin(),acti_vec.end(),[](const Acti& a,const Acti& b){return a.second < b.second;});//按結(jié)束時間對所有活動排序。 vector<vector<Acti>> classroom;//教室列表。vector<Acti> classroom1;classroom1.push_back(*acti_vec.begin());//初始化第一個教室，將結(jié)束時間最早的活動放入。 classroom.push_back(classroom1);//將第一個教室加入教室列表。for(int i = 1;i<(int)acti_vec.size();i++)//遍歷一遍活動列表。 {int j;for(j = 0;j < (int)classroom.size();j++){if(acti_vec[i].first >= (*(classroom[j].end()-1)).second)//如果該活動的開始時間比某教室目前為止最后一個活動結(jié)束結(jié)束時間晚，則加入該教室。 {classroom[j].push_back(acti_vec[i]);break;}} if(j == (int)classroom.size())//如果無法加入當前任何一個教室，則需要一個新的教室。 {vector<Acti> classroom_temp;classroom_temp.push_back(acti_vec[i]);classroom.push_back(classroom_temp);}} for(int i = 0;i < (int)classroom.size();i++)//對每一個教室，按起始時間 結(jié)束時間輸出每一個活動。 {cout<<"classroom "<<i+1<<":"<<endl;for(int j = 0;j < (int)classroom[i].size();j++){cout<<classroom[i][j].first<<" "<<classroom[i][j].second<<endl;}} }int main() {vector<Acti> acti_vec = {{1,4},{3,5},{0,6},{5,7},{3,9},{5,9},{6,10},{8,11},{8,12},{2,14},{12,16}};party(acti_vec);return 0; }

?　　在本題解法的第一次實現(xiàn)中犯了一個錯誤，錯誤的使用了迭代器，然而，由于在遍歷的過程中，要向classroom的vector中添加元素，當vector被修改后，原先的迭代器都會失效，所以不能使用迭代器，而改用int下標。

　

轉(zhuǎn)載于:https://www.cnblogs.com/StartoverX/p/4608412.html

總結(jié)

以上是生活随笔為你收集整理的[算法导论]练习16.1-4 活动教室分配（区间着色问题）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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