501. 区间选点
时间限制：1000 MS 内存限制：64 MB
题目描述
# 区间选点 ## 题目描述 给定 $N$ 个闭区间 $[a_i,b_i]$，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 位于区间端点上的点也算作区间内的点。 请输出需要选择的点的最小数量。 ## 输入格式 从文件 `points.in` 中读入数据。 第一行包含一个整数 $N$，表示区间的数量。 接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个闭区间的两个端点。 ## 输出格式 输出到文件 `points.out`。 输出一个整数，表示覆盖所有区间所需的最少点数。 ## 数据范围 - $1 \le N \le 10^5$。 - $-10^9 \le a_i \le b_i \le 10^9$。 - 所有区间均包含端点。 ## 样例输入 ``` 3 -1 1 2 4 3 5 ``` ## 样例输出 ``` 2 ``` ## 样例说明 选择点 $1$ 和 $3$ 即可使每个区间内至少包含一个选出的点。由于区间 $[-1,1]$ 与 $[2,4]$ 不相交，至少需要选择两个点，因此答案为 $2$。 ## 资源限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。