区间分组题解

思路

考虑任意一个坐标，同时覆盖该坐标的所有闭区间两两相交，因此它们必须被分到不同组。于是最少分组数至少是任意坐标处覆盖区间数量的最大值。

反过来，按左端点从小到大处理区间，并优先复用右端点最小且已经与当前区间分离的组。如果没有组可复用，那么所有已有组的最后一个区间都覆盖当前左端点，新区间与它们同时相交，确实必须新建一组。因此所需组数恰好等于最大同时覆盖数量。

题目只要求输出组数，所以直接统计每个坐标处有多少个闭区间覆盖即可。

做法

对每个闭区间 $[L,R]$，在差分数组的 $L$ 处加一，在 $R+1$ 处减一。按坐标从小到大求前缀和，前缀和就是当前坐标被多少个区间覆盖。所有前缀和的最大值即为答案。

使用 $R+1$ 而不是 $R$ 进行减法，保证两个只在端点相交的闭区间会在该端点同时计入。

正确性证明

设最大同时覆盖数量为 $D$。在达到该数量的坐标上，有 $D$ 个区间两两相交，它们不可能位于同一组，所以任何方案至少需要 $D$ 组。

按左端点顺序进行贪心分组。处理新区间时，若某组最后区间的右端点严格小于当前左端点，则可复用该组；否则必须新建一组。每次新建第 $k$ 组时，前 $k-1$ 组最后的区间右端点都不小于当前左端点，而它们的左端点都不大于当前左端点，因此这些区间与当前区间共同覆盖当前左端点。此时至少有 $k$ 个区间同时覆盖一点，所以 $k\le D$。故存在只用 $D$ 组的方案。

结合上下界，最少分组数等于 $D$。差分前缀和准确统计每个坐标的覆盖数量，因此算法输出正确。

复杂度

设坐标上界为 $V=2\times 10^5$。时间复杂度为 $O(n+V)$，空间复杂度为 $O(V)$。