切換
舊版
前往
大廳
主題

ZeroJudge - e563: 12694 - Meeting Room Arrangement　解題心得

Not In My Back Yard | 2019-12-14 15:18:48 | 巴幣 0 | 人氣 289
題目連結：
題目大意：
給定一正整數 n （1 ≦ n ≦ 100），代表有 n 筆測試資料。每筆測資有若干列（不超過 21列），每列給定非負兩整數 s 、 f （0 ≦ s ≦ 9 ，1 ≦ f ≦ 10 且 s ＜ f。當 s ＝ f ＝ 0 時，代表測資的結尾），代表一項活動的開始時間以及結束時間。

可用時間編號為 0 ～ 10 。試問，最多可以安排多少活動？

範例輸入：
3
0 6
5 7
8 9
5 9
1 2
3 4
0 5
0 0
6 10
5 6
0 3
0 5
3 5
4 5
0 0
1 5
3 9
0 0
範例輸出：
4
4
1
解題思維：
我們可以將這些活動以結束時間由早到晚排序，接著對結束時間一樣的由開始時間早到晚排序。

接著就一一掃過這些活動，並宣告一變數用來儲存現在的時間。當有一活動的開始時間 ≧ 現在的時間，現在的時間就更新為該活動的結束時間。並將活動數 ＋ 1 。

掃完之後的活動總數即是所求。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得#排序（Sorting）#貪心演算法（Greedy Algorithm）
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

早瀨優香

看更多

更多創作

追蹤 創作集
其他創作
作品資料夾