#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
📊 数据规模与约定
| 数据范围 | 约定 | 占比 |
|---|---|---|
| 对于 的数据 | 1 <= n <= 2e5,-1e9 <= l_i <= r_i <= 1e9 | 100% |