题目描述

在 $x$ 轴上给你 $n$ 条线段，每条线段由左右 2 个端点 $[l_i, r_i]$ 给出，现在希望选出最少的线段，可以覆盖 $1,2,3,...,m$ 中所有点

输入格式

第一行两个正整数 $m, n(1 \le m \le 10^{12}, 1 \le n \le 2\times10^5)$，用空格隔开，表示要覆盖的点的个数和线段的个数

接下来 $n$ 行，每行两个正整数 $l_i, r_i(1 \le l_i, r_i \le m)$，用空格隔开，表示第 $i$ 条线段的左右端点

输出格式

一行一个整数，表示最少选择的线段数，数据保证有解

3 3
1 2
2 3
2 2

2

4 2
1 4
1 4

1

6 4
2 4
1 2
3 6
1 3

2

提示

【样例解释】

• 第 1 组样例选择 [1, 2], [2, 3]
• 第 2 组样例选择 [1, 4]
• 第 3 组样例选择 [1, 3], [3, 6]
• 考虑如下几种贪心策略哪个是正确的
• 1）把线段长度从大到小排序，然后从大到小选择
• 2）把线段按左端点 $l_i$ 从小到大排序，然后从左往右选择
• 3）把线段按右端点 $r_i$ 从大到小排序，然后从右往左选择

数据规模与限制

• $1 \le n \le 10^5$
• 1s, 1024KiB for each test case.

来源