区间最大不相交问题

题目描述

给定 $n$ 个闭区间 $[L_i,R_i]$。请选择尽量多的区间，使任意两个被选区间没有公共点，求最多可以选择多少个区间。

输入格式

第一行输入一个整数 $n$。

接下来 $n$ 行，每行输入两个整数 $L_i,R_i$，表示一个闭区间。

输出格式

输出一个整数，表示最多可以选择的两两不相交区间数量。

样例输入 1

4
1 3
4 5
4 7
8 9

样例输出 1

3

数据范围

对于全部数据，$1\le n\le 2\times 10^5$，$1\le L_i\le R_i\le 2\times 10^5$。