UVA-12694 - Meeting Room Arrangement

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20161004 大學程式能力檢定 CPE」題目。

題意概要

學校裡有一間會議室必須事先登記使用使用，由於會議室每天能使用的時間只有 $10$ 個小時，且有很多登記要使用，所以最佳使用的方式就是：讓使用的會議最多。假設會議室能使用的時間從 $0$～$10$（$10$ 個小時）。給你事先登記的每個會議的開始、結束時間，請你寫一個程式算出這天中最多能舉行多少個會議，當然能舉行的會議彼此時間不能有重疊。

• 分析：本題為簡單的貪婪法 (Greedy Method) 實作。由題意先將所有的登記按照「愈早開始的優先；起始時間先同，則愈早結束優先」的方式排序排序，排序完畢後，由起始時間開始，每次取「上一個登記結束時間後」的第一個登記即可。本題建議使用 std::pair 以方便存取每一個登記的起始與結束時間，需要 #include <utility>。

Input

The first line is a positive integer $n$ ($1 \le n \le 100$) which determines the number of days (test cases). Each test case consists of the time of the candidate events (less than $20$ events). Each event time includes $2$ integers which are start time(s) and finish time(f), $0 \le s \le 9$, $1 \le f \le 10$ and $s < f$. The line containing 0 0 indicates the end of each test case. Note that an event must use at least $1$ hour.

Output

For each test case, print out the maximum number of events that can be arranged in the meeting room.

Sample Input

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

Sample Output

4
4
1

Sample Output

0 - Wonderful.
379749833583241 - Wonderful.
3909821048582988049 - Wonderful.
10 - Simple.