721 . 原料廠商
TopCoder
Tags
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
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
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 |