小彥是個學分的精算大師，他發現只要再通過這堂重補修門課，就能夠順利畢業。這門課包含了$N$個作業，小彥為每個作業都分配了一個時段，從第$s_i$天下午開始做，然後到第$t_i$天上午繳交。當天要繳交的作業與同天開始做作業不會重疊。
小彥除了是個學分精算大師之外，他還非常擅長一心多用。雖然小彥顯然可以直接一心$N$用直接解決所有作業。但他發現依據這堂課的配分方式，只需要完成一半的作業就可以及格了。小彥想集中心思在一部分的作業上，因此他想要在完成一半以上作業的同時，讓每一天的作業數量盡可能的少，請問在最多作業的那天的作業數量最少為何?
第一行有一個正整數$N$，代表作業的數量。
接下來有$N$行，第$i$行有兩個正整數$s_i$和$t_i$，代表第$i$個作業開始與繳交的時間。
測資限制
所有輸入皆為正整數
$N \leq 1 \times 10^5$
$s_i,t_i \leq 10^9,1\leq i \leq N$
輸出一行包含一整數，代表在最多作業的那天的作業數量最少為何。
6 1 2 1 3 2 7 1 4 4 5 3 6
2
4 1 2 1 2 2 3 2 3
1
6 3 9 1 6 1 5 2 5 4 6 2 8
3
本題共有三組子任務，條件限制如下所示。
子題一 21%
$N \leq 20$
子題二 30%
$N \leq 2 \times 10^3$
子題三 49%
無額外限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||