/ SB域 / 题库 /

【模板】最多不相交区间

【模板】最多不相交区间

【试题描述】给定N个闭区间,最多能选出多少个不相交区间。
【输入格式】输入第一行只包括一个整数N。
接下来N行每行包括两个整数a,b用一个空格隔开,描述一个闭区间[a,b]。
【输出格式】输出只包括一个整数为最多不相交区间个数。
【样例输入】

4
4 9
9 10
13 19
10 17

【样例输出】

2

【注释】
* 对于30%的数据,N<=100。
* 对于80%的数据,N<=3000。
* 对于100%的数据,N<=200000。