#TX00008. 电力覆盖(最少电线塔覆盖所有线路)

电力覆盖(最少电线塔覆盖所有线路)

题目 电力覆盖(最少电线塔覆盖所有线路)

📄 题目描述

给出 n 条线段区间 [l_i, r_i]。你需要选尽可能少的点,使每条线段至少包含一个所选点。求最少点数。

⌨️ 输入格式

第一行一个整数 n。 接下来 n 行,每行两个整数 l_i, r_i。

📤 输出格式

输出一个整数,表示最少点的数量。


🧪 样例

14
44 49
50 51
2 7
47 48
16 24
50 51
17 31
40 43
3 11
27 28
16 21
20 23
32 40
40 49
6

📊 数据规模与约定

数据范围 约定 占比
对于 100%100\% 的数据 1 <= n <= 2e5,-1e9 <= l_i <= r_i <= 1e9 100%