1308 - 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。输出 需要移除区间的最小数量，使剩余区间互不重叠 。（左右边界一样时不算重叠）

输入

第一行为一个整数n，表示有多少个区间

以下n行每行2个整数，表示区间的起始坐标和终止坐标

输出

需要移除区间的最小数量，使剩余区间互不重叠

样例

输入

4
1 2
2 3
3 4
1 3

输出

1

输入

3
1 2
1 2
1 2

输出

2

输入

2
1 2
2 3

输出

0

提示

1 <= intervals.length <= 10^5

intervals[i].length == 2

-5 x 10^4 <= starti < endi <= 5 x 10^4

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题