721 . 原料廠商

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

hellowin

User's AC Ratio

94.7% (18/19)

Submission's AC Ratio

17.2% (22/128)

Tags

apcsc apcsc-greedy

Description

小鴨工廠專門製造黃色小鴨，他們必須和塑膠原料廠訂購塑膠。一共有 N 家塑膠原料廠，其中第 i 家能從第 si 天供貨到第 ti 天。

小鴨工廠想要選一些原料廠當合作對象。假設最早能供貨的原料廠開始時間是第 S 天，能供貨到最晚的原料廠結束於第 T 天，小鴨工廠希望從 S 到 T 的每天都要與一家原料廠合作。在此限制下，小鴨工廠希望合作廠商愈少愈好，請你回答至少需要幾家廠商。

Input Format

輸入第一行一個整數是 N，代表原料廠商數量。

接著有 N 行每行兩個空白相隔的整數 si,ti，代表第 i 家廠商的供貨時段 (1≤i≤N)。

輸入保證 1≤N≤1000，1≤si≤ti≤105。

特別注意到輸入並沒有保證兩家廠商不會有相同供貨時間。

Output Format

輸出一行一個整數代表最少的合作廠商，如果無論如何都不可能則請輸出 −1。

Sample Input 1

5
2 4
3 7
5 10
6 8
10 13

Sample Output 1

3

Sample Input 2

4
1 3
2 4
6 8
7 9

Sample Output 2

-1

Hints

Problem Source

TNFSH OJ

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
Submit
Back to Top