题目描述

给定一个区间的集合 $intervals$ ，其中 $intervals[i] = [starti, endi]$ 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

注意  只在一点上接触的区间是  不重叠的 。例如 $[1, 2]$ 和 $[2, 3]$ 是不重叠的。

输入格式

第一行一个整数 $n$，表示共有多少个区间；

接下来的 $n$ 行，每行两个空格隔开的整数表示区间的左右端点。

输出格式

一行一个整数表示答案。

示例 1:

4
1 2
2 3
3 4
1 3

1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

3
1 2
1 2
1 2

2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

2
1 2
2 3

0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• $1 <= intervals.length <= 10^5$
• $intervals[i].length == 2$
• $-5 * 10^4 <= start_i < end_i <= 5 * 10^4$

SOURCE

无重叠区间