‹ 上一题下一题 ›

j01294. 无重叠区间未做

1000 ms 256 MB 测试点 10 通过率 34% 5级·贪心经典模型贪心贪心与排序/堆的配合

文件读写输入j01294.in输出j01294.out

题目描述

时间轴上有 $n$ 个区间 $[l_{i}, r_{i}]$ （端点相触不算重叠）。最少移除多少个区间，能使剩余区间两两不重叠？

输入格式

第一行一个整数 $n$ ；接下来 $n$ 行，每行两个整数 $l_{i}, r_{i}$ 。

输出格式

一行一个整数：最少移除的区间数。

样例

输入

输出

数据范围

$1 \leq n \leq 2 \times 1 0^{5}$ ， $0 \leq l_{i} \leq r_{i} \leq 1 0^{9}$

输入

输出

答案