d046: P_4_4 幾場華山論劍(activity selection)
Tags : ch4
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-12 22:36

Content

自從華山論劍聲名大噪之後,想參加的人絡繹不絕,因此華山派決定每年都舉辦非常 多場的華山論劍,
每一場都有自己的開始時間與結束時間,參加者必須全程在場,所以不能在同一時間參加兩場。

令狐沖拿到了今年所有場次的資料,希望能參加越多場越好,以便盡速累積經驗值,請你幫忙計算最多可以參加幾場。

請注意,所挑選活動必須完全不重疊,兩場活動只在端點重疊也是不可以同時參加的,也就是說前一場的結束時間必須小於下一場的開始時間。

Input

第一行是一個正整數 n,代表一共舉辦了 n 場華山論劍,

接下來 n 行,每 行兩個非負整數 s 與 t,代表這場活動的時間區間是 [s,t],兩數字間以空白間格。

n 不超過 105,s < t < 109

Output

 最多參加幾場活動。

Sample Input #1
4
1 4
0 3
3 4
4 6
Sample Output #1
2
測資資訊:
記憶體限制: 256 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:
ch4
出處:
Prof. Wu [管理者:
ktlai (K.我已霸榜.Tlai)
]


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