【聲明：本文為原創(chuàng)文章,未經同意,嚴禁轉載和抄襲,違者將追究其法律責任】

蘇世機試小課堂，考研機試不再慌！

公主號：蘇世學社考研? 蘇世計算機考研

今年寒假不AC

Time Limit: 2000/1000 MS

?(Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

題目描述

“今年寒假不AC？”
“是的?！?br>“那你干什么呢？”
“看德瑪西亞杯呀，笨蛋！”
“@#$%^&*%...”

確實如此，德瑪西亞杯來了，召喚師們的節(jié)日也來了，估計很多ACMer也會拋開代碼進入直播間了。

作為一名合格的召喚師，一定想看盡量多的完整的比賽，當然，作為新時代的好青年，你一定還會看一些其它的節(jié)目，比如新聞聯(lián)播（永遠不要忘記關心國家大事）、令人心動的offer、奇葩說，以及奔跑吧·黃河篇等等，假設你已經知道了所有你喜歡看的電視節(jié)目的轉播時間表，你會合理安排嗎？（目標是能看盡量多的完整節(jié)目）

輸入

輸入數(shù)據包含多個測試實例，每個測試實例的第一行只有一個整數(shù)n(n<=100)，表示你喜歡看的節(jié)目的總數(shù)，然后是n行數(shù)據，每行包括兩個數(shù)據Ti_s,Ti_e (1<=i<=n)，分別表示第i個節(jié)目的開始和結束時間，為了簡化問題，每個時間都用一個正整數(shù)表示。n=0表示輸入結束，不做處理。

輸出

對于每個測試實例，輸出能完整看到的電視節(jié)目的個數(shù)，每個測試實例的輸出占一行。

樣例輸入

12

1 3

3 4

0 7

3 8

15 19

15 20

10 15

8 18

6 12

5 10

4 14

2 9

0

樣例輸出

5

答案

①讀題:

根據每個節(jié)目的開始時間和結束時間求最多能看幾個節(jié)目。

②想出思路：

按照結束時間排序，從頭開始遍歷，如果下一個節(jié)目開始時間晚于上一個節(jié)目結束時間，則可以看下一個節(jié)目。如果不行，跳過繼續(xù)往后遍歷。

③動手編程：

④測試樣例：

拿題目中的樣例輸入進行測試：

⑤提交代碼：

進入下面的鏈接提交代碼：

http://acm.hdu.edu.cn/showproblem.php?pid=2037

⑥返回評測結果：

至此，這道題我們就已經完成了。

本題總結

本題中將一個節(jié)目的開始時間和結束時間做成結構體，內置按結束時間排的排序方式，用貪心算法依次遍歷每個節(jié)目符合條件就加入，不符合就跳過，最后能得到最大值。

未完待續(xù)

蘇世學社旗下品牌，專注于計算機考研

計算機考研一手資訊，原創(chuàng)高質量干貨

深度的學習分享丨咨詢前輩丨個性化指導