10564 - Homework Arrangement
|
Time |
Memory |
| Case 1 |
1 sec |
32 MB |
| Case 2 |
1 sec |
32 MB |
| Case 3 |
1 sec |
32 MB |
| Case 4 |
3 sec |
32 MB |
| Case 5 |
3 sec |
32 MB |
| Case 6 |
3 sec |
32 MB |
Description
身在資工系的小傑,學期中常有寫不完的作業,每份作業都有繳交期限。認真的小傑對課業成績非常在意,總是盡力完成所有作業,可是到了期中他發現,就算不吃飯、不上課、不睡覺,也無法在期限內完成所有作業,於是他必須採取棄保策略,他已經預算好每個作業所要花的時間,請你算出他最多能交出幾份作業。
舉例來說,如範例一,小傑可以在時間0 ~ 2完成作業一,時間2 ~ 3完成作業二,此時就無法完成作業三,因為它的期限是在時間4,如圖 (a) 所示;另一種策略是:時間0 ~ 2完成作業一,時間2 ~ 4完成作業三,如圖 (b) 所示。
圖 (a)
圖 (b)
Input
第1行輸入一個正整數 n,代表作業份數
第2 ~ n + 1行,每行兩個正整數,分別表示這個作業的繳交期限和完成它所需的時間,單位皆為一小時,可以假設小傑能從時間 0 開始不眠不休拼命地趕作業。
限制:n ≤ 1,000,000,所有整數皆可存於32-bit signed integer (ex: int in C++)
Output
輸出一個整數代表最多能完成的作業份數。(剛好在作業繳交期限時間點寫完的作業算是完成的)
Tags