722 . 胖達在做 foodpanda

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

apcsc apcsc-greedy

Description

胖達是一位全職的 foodpanda 外送員，某天醒來時，胖達突然發現他有了預知未來的超能力，能知道當天每一張外送單的開始和結束時間，它決定用這能力來最大化一天能送的單量。胖達接的任何兩張單時間都不能有重疊，你能幫它算出它一天最多能送幾張單嗎？

Input Format

第一行有一個整數 N(1≤N≤5×105)，代表今天胖達可能接到的外送任務數量。
接下來 N 行，每行有兩個整數 si,ei(1≤si<ei≤2×109)，代表第 i 個外送任務的開始與結束時間。

Output Format

請輸出一個整數 M，代表胖達今天所能完成的最大外送任務數量。

Note：開始與結束時間是 exclusive 的，也就是說胖達可以完成在（1 開始，10 結束）與（10 開始，20 結束）這兩項外送任務。

Sample Input 1

3
1 2
2 3
3 4

Sample Output 1

3

Sample Input 2

4
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

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
Submit
Back to Top