无重叠区间

题目描述

给定 n 个区间，第 i 个区间为 [l_i, r_i]（保证 l_i < r_i）。

定义两个区间 [l1, r1] 与 [l2, r2] 互不重叠，当且仅当满足 r1 ≤ l2 或 r2 ≤ l1（端点恰好相接不算重叠）。

你可以删除其中若干个区间，使得剩下的区间两两互不重叠。

请你求出最少需要删除多少个区间，才能达到上述要求。

输入格式

第一行一个正整数 n，表示区间的个数。

接下来 n 行，每行两个整数 l_i 和 r_i，描述第 i 个区间。

输出格式

输出一行一个整数，表示最少需要删除的区间数量。

样例

4
1 2
2 3
3 4
1 3

1

3
1 2
2 3
3 4

0

样例解释

• 样例 1：删除区间 [1,3] 后，剩下的 [1,2]、[2,3]、[3,4] 两两互不重叠（端点相接不算重叠），因此答案为 1。
• 样例 2：三个区间本来就互不重叠，无需删除，答案为 0。

数据范围

• 1 ≤ n ≤ 10^5
• -10^9 ≤ l_i < r_i ≤ 10^9

提示

经典贪心：将所有区间按右端点从小到大排序，然后依次选择"与已选区间不重叠"的区间，记录最多能保留的数量 k，答案即为 n - k。