502. 最大不相交区间数量
时间限制：1000 MS 内存限制：64 MB
题目描述
# 最大不相交区间数量 ## 题目描述 给定 $N$ 个闭区间 $[a_i,b_i]$，请你从中选择若干区间，使得选中的区间两两没有公共点。 由于这些区间是闭区间，端点也属于区间。因此，两个区间即使仅有端点重合，也不能同时选择。 请你求出最多可以选择多少个区间。 ## 输入格式 从文件 `disjoint.in` 中读入数据。 第一行包含一个整数 $N$，表示区间的数量。 接下来 $N$ 行，每行包含两个整数 $a_i,b_i$，表示一个闭区间的两个端点。 ## 输出格式 将答案输出到文件 `disjoint.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,1]$ 和 $[2,4]$，共选择 $2$ 个区间。 区间 $[2,4]$ 和 $[3,5]$ 有公共点，不能同时选择，因此最多可选择 $2$ 个区间。 ## 时间与内存限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。