Lecture Halls （會議安排）??

時間限制(普通/Java):1000MS/10000MS ? ? 運行內(nèi)存限制:65536KByte
總提交: 38 ? ? ? ?? ? 測試通過: 20

描述

?

假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設(shè)計一個有效的算法進行安排。(這個問題實際上是著名的圖著色問題。若將每一個活動作為圖的一個頂點，不相容活動間用邊相連。使相鄰頂點著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會場數(shù)。)

編程任務(wù)： 對于給定的k個待安排的活動，編程計算使用最少會場的時間表。

?

輸入

輸入數(shù)據(jù)是由多組測試數(shù)據(jù)組成。每組測試數(shù)據(jù)輸入的第一行有1 個正整數(shù)k，表示有k個待安排的活動。接下來的k行中，每行有2個正整數(shù)，分別表示k個待安排的活動開始時間和結(jié)束時間。時間以0 點開始的分鐘計。

輸出

對應(yīng)每組輸入，輸出的每行是計算出的最少會場數(shù)。

樣例輸入

?

5 1 23 12 28 25 35 27 80 36 50

?

樣例輸出

?

3

?

題目上傳者

crq

#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int INF = 0x7fffffff; const int maxn = 1000000; int n; int v[maxn];int main() {int from, to, i, res;while(scanf("%d", &n) != EOF) {memset(v, 0, sizeof(v));for(i = 0; i < n; i++) {scanf("%d%d", &from, &to);v[from] += 1;v[to] += -1;}res = 0;int maxv = -INF;for(i = 0; i < maxn; i++) {res += v[i];if(res > maxv) {maxv = res;}}cout << maxv << endl;}return 0; }

?

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

總結(jié)

以上是生活随笔為你收集整理的Lecture Halls的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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