921
會場安排問題
會場安排問題
時間限製：3000 ms | 內存限製：65535 KB
難度：4
- 描述
- 學校的小禮堂每天都會有許多活動，有時間這些活動的計劃時間會發生衝突，需要選擇出一些活動進行舉辦。小劉的工作就是安排學校小禮堂的活動，每個時間最多安排一個活動。現在小劉有一些活動計劃的時間表，他想盡可能的安排更多的活動，請問他該如何安排。
- 輸入
- 第一行是一個整型數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時間開始
這道題一開始提交出錯，因為我誤解了。我以為開始與結束時間相同就不能安排，
現在我把那段代碼注釋掉，AC了！
查看代碼---運行號：252698----結果：Accepted
運行時間：2012-10-06 16:38:52 | 運行人:huangyibiao
01.#include <iostream>
02.#include <algorithm>
03.#include <cstdio>
04.using
namespace std;
05.
06.struct
Activity
07.{
08.int
begin;//活動開始時間
09.int
end; //活動結束時間
10.};
11.
12.int
compare(const
void *p1, const
void *q1)
13.{
14.Activity *p = (Activity *)p1;
15.Activity *q = (Activity *)q1;
16.
17.return
p->end > q->end ? 1 : -1;
18.}
19.
20.int
main()
21.{
22.int
sample;
23.cin >> sample;
24.
25.while
(sample--)
26.{
27.int
nNumOfAct;
28.cin >> nNumOfAct;//活動數量
29.
30.Activity *act =
new Activity[nNumOfAct];
31.for
(int
i = 0; i < nNumOfAct; i++)
32.scanf("%d %d",
&act[i].begin, &act[i].end);
33.
34.qsort(act, nNumOfAct,
sizeof(Activity), compare);
//從小到大排序
35.
36.int
cnt = 1, i, j;//至少能安排一個活動
37.int
e = act[0].end;
38.for
(i = 1; i < nNumOfAct; i++)
39.{
40.//if (act[i].begin == act[i].end)
41.//continue;//如果開始與結束的時候相同，那麼就不能安排
42.if
(act[i].begin > e)
43.{
44.cnt++;
45.e = act[i].end;
46.}
47.
48.}
49.cout << cnt << endl;
50.delete
[]act;
51.}
52.return
0;
53.}
最後更新：2017-04-02 15:14:54