TopCoder

aacpschool

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

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

Sample Output 1

Sample Input 2

4
1 3
3 8
3 5
5 7

Sample Output 2

Hints

Problem Source

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~11	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	2000	524288	65536	1 2
1	2000	524288	65536	1 2
2	2000	524288	65536	2
3	2000	524288	65536	2
4	2000	524288	65536	2
5	2000	524288	65536	2
6	2000	524288	65536	2
7	2000	524288	65536	2
8	2000	524288	65536	2
9	2000	524288	65536	2
10	2000	524288	65536	2
11	2000	524288	65536	2

722 . 胖達在做 foodpanda