721 . 原料廠商

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

hellowin

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

31.2% (5/16)

Tags

apcsc apcsc-greedy

Description

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

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

Input Format

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

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

輸入保證 $1\le N\le 1000$，$1\le s_i\le t_i\le 10^ 5$。

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

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