#P8171. [POI2023] Zapobiegliwy student

[POI2023] Zapobiegliwy student

题目描述

考虑如下的一个简单问题:

你有 nn 个线段在数轴上,你要选出尽量多的线段,使它们两两不交。

我知道你一定会做,但你需要解决这个:

你有 nn 个线段在数轴上,你要选出尽量多的线段对 (ui,vi)i=1k(u_i,v_i)_{i=1}^k,即最大化 kk。

满足 k+1k+1 个要求:

  • u1,u2,⋯ ,uku_1,u_2,\cdots,u_k 两两不交。
  • v1,u2,u3,⋯ ,ukv_1,u_2,u_3,\cdots,u_k 两两不交。
  • u1,v2,u3,u4,⋯ ,uku_1,v_2,u_3,u_4,\cdots,u_k 两两不交。
  • ⋯\cdots
  • u1,u2,⋯ ,uk−1,vku_1,u_2,\cdots,u_{k-1},v_k 两两不交。

其中 ∀i\forall i,uiu_i 与 viv_i 不能相同。

输入格式

第一行一个正整数 n(n≥2)n(n\geq2)。

接下来 nn 行每行两个正整数 ai,bi(1≤ai<bi≤109)a_i,b_i(1\leq a_i<b_i\leq10^9),表示一个线段的两个端点。

两个线段 i,ji,j 不交当且仅当 bi≤ajb_i\leq a_j 或 bj≤aib_j\leq a_i。

输出格式

第一行一个正整数 kk。

样例 #1

样例输入 #1

8
1 5
3 10
4 8
9 12
11 16
14 15
20 22
15 21

样例输出 #1

3
子任务编号 限制 分值
1 n≤3000n\leq3000 40
2 n≤500000n\leq500000 60