e076: Q-4-20. 監看華山練功場
Tags : greedy
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2024-03-04 02:18

Content

華山派有 n 個弟子,每個弟子的練功時間都不盡相同,第 i 個弟子到練功場所練功的時間是區間[s(i),t(i)]。最近華山頗不平靜,掌門岳不群要求令狐沖找一些弟子練功時順便監看練功場,對於想要監看的時間區間[x,y],請問他最少只要找幾位弟子,這些弟子的練功時間就可以涵蓋整個[x,y]。

Time limit: 1 秒

Input

第一行是個正整數 n,第二行是兩個整數 x 與 y,接著的 n 行每一行有兩個整數 s(i)與 t(i),同行相鄰兩數之間空白區隔。n 不超過 1e5,0 <= x < y <= 1e9, 且對所有 i,0 <= s(i) < t(i) <= 1e9。

Output

練功時間可以涵蓋[x,y] 的最少的弟子數。如果無解輸出-1。

Sample Input
範例一:
5
1 10
0 3
1 5
5 7
8 9
6 10

範例二:
5
1 10
0 3
1 5
5 7
8 9
8 10
Sample Output
範例一:
3

範例二:
-1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <10M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
greedy
出處:
AP325 [管理者:
mcjksieu005 (mcjksieu005)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」