题目理解

我们有 $n$ 个区间 $[l_i, r_i]$，要选出 $m$ 个区间，使得它们有公共交点（存在一个 $x$ 被所有选中的区间包含）。

花费 = 被选中的区间中最长的长度 − 被选中的区间中最短的长度。

我们要最小化这个花费。

思路分析

1. 问题转化

如果我们选定了 $m$ 个区间，它们有公共点 $x$，那么 $x$ 一定属于这 $m$ 个区间的交集。
为了最小化 max_length − min_length，一个常见的思路是：

• 将区间按长度排序。
• 使用**双指针（滑动窗口）**的方法，枚举最短区间和最长区间，并检查在长度区间 $[len_{min}, len_{max}]$ 内能否选出 $m$ 个区间有公共点。

2. 排序与双指针

我们按区间长度升序排序，这样我们枚举的区间在数组中是连续的，方便控制 max_len − min_len。

假设排序后的区间序列是 $I_1, I_2, \dots, I_n$（按长度从小到大）。

我们固定左指针 $i$ 表示最短区间，右指针 $j$ 表示最长区间，从 $i$ 开始向右扩展 $j$，直到我们找到某个 $j$ 使得在区间 $[i..j]$ 中能选出 $m$ 个区间有公共点。

3. 如何判断“m个区间有公共点”

这是一个经典问题：给定一堆区间，问是否存在一个点被至少 $m$ 个区间覆盖。

我们可以用扫描线方法：

• 将每个区间 $[l, r]$ 拆成两个事件：在 $l$ 处覆盖数 +1，在 $r+1$ 处覆盖数 −1。
• 按坐标从小到大扫描，维护当前覆盖数，如果某个时刻覆盖数 $\ge m$，则存在公共点。

但这里我们是在区间集合 $[i..j]$ 中做查询，$i,j$ 会变化，所以需要动态维护。

4. 动态维护区间覆盖数

当 $j$ 增加时，加入区间 $I_j$；当 $i$ 增加时，移除区间 $I_i$。

我们可以用一个线段树或平衡树（因为坐标范围可能到 $10^9$，需要离散化）来维护：

• 区间加操作（加入区间时在 $[l, r]$ 上加 1，删除时减 1）
• 全局最大值查询（即某个点的最大覆盖数）

如果全局最大值 $\ge m$，说明当前 $[i..j]$ 中存在一个点被至少 $m$ 个区间覆盖。

5. 算法步骤

1. 按区间长度排序。
2. 离散化所有 $l_i, r_i+1$（因为事件是 $l$ 和 $r+1$）。
3. 双指针 $i=1, j=0$。
4. 当 $j < n$：
   • 不断右移 $j$，加入区间 $I_j$（线段树区间加 1），直到当前覆盖最大值 $\ge m$。
   • 如果满足，更新答案 $ans = \min(ans, len_j - len_i)$。
   • 右移 $i$，移除区间 $I_i$（线段树区间减 1）。
5. 输出答案（如果从未满足则输出 -1）。

时间复杂度：排序 $O(n \log n)$，双指针 $O(n)$，每次操作线段树 $O(\log n)$，总 $O(n \log n)$。

6. 实现细节

• 离散化时注意 $r+1$ 也要加入。
• 线段树维护区间加、全局最大值。
• 注意区间长度是 $r_i - l_i$。