普及⏱ 1000ms💾 256MB#P5057

题目描述

给定 $n$ 个闭区间,最少移除多少个区间可使剩下的区间两两不重叠(端点相接不算重叠)?

输入格式

第一行整数 $n$;接下来 $n$ 行每行两个整数 $l, r$

输出格式

一行一个整数,即最少移除数。

数据范围

$$1 \le n \le 10^5,\ 0 \le l \le r \le 10^9$$

样例输入 #1
1
0 1000000000
样例输出 #1
0
样例输入 #2
2
1 5
5 9
样例输出 #2
0