活动区间选择

入门⏱ 1000ms💾 256MB#P2278🏷️ 排序贪心

题目描述

数轴上有 $n$ 条线段,选尽可能多的两两不重合(端点可重合)的线段,输出最大个数。

输入格式

第一行一个正整数 $n$; 以下 $n$ 行,每行两个整数 $a_i, b_i$,为线段左右端点。

输出格式

一行,一个整数:最大可选条数。

数据范围

$$n \le 10^6,\ 0 \le a_i \le b_i \le 10^9$$

样例输入 #1
3
0 2
2 4
1 3
样例输出 #1
2
样例输入 #2
1
0 1000000000
样例输出 #2
1