题目描述

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

注意

• 只在一点上接触的区间是 不重叠 的。例如 [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