722 . 胖達在做 foodpanda
TopCoder
Tags
Description
胖達是一位全職的 foodpanda 外送員，某天醒來時，胖達突然發現他有了預知未來的超能力，能知道當天每一張外送單的開始和結束時間，它決定用這能力來最大化一天能送的單量。胖達接的任何兩張單時間都不能有重疊，你能幫它算出它一天最多能送幾張單嗎？
Input Format
第一行有一個整數 $N(1 \leq N \leq 5 \times 10^ 5)$，代表今天胖達可能接到的外送任務數量。
接下來 $N$ 行，每行有兩個整數 $s_i , e_i(1 \leq s_i < e_i \leq 2 \times 10^ 9)$，代表第 $i$ 個外送任務的開始與結束時間。
Output Format
請輸出一個整數 $M$，代表胖達今天所能完成的最大外送任務數量。
Note：開始與結束時間是 exclusive 的，也就是說胖達可以完成在（$1$ 開始，$10$ 結束）與（$10$ 開始，$20$ 結束）這兩項外送任務。
Sample Input 1
3
1 2
2 3
3 4
1 2
2 3
3 4
Sample Output 1
3
Sample Input 2
4
1 3
3 8
3 5
5 7
1 3
3 8
3 5
5 7
Sample Output 2
3
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~11 | 無額外限制 | 100 |