给定n个区间，寻找两个点使区间交集数量之和最大化

这题我之前竞赛里也遇到过，一开始也想直接贪心选最优单点再选次优，结果发现踩了坑——最优单点覆盖的区间和次优点重叠太多，总和反而不如两个互补的点。下面给你详细拆解正确的解法思路：

首先得明确目标：我们要选两个点，让至少被其中一个点覆盖的区间总数最大（对应你示例里的“两次选择的区间交点数量之和”——本质是两个点覆盖的区间并集大小）。等价于最大化 |S(x)| + |S(y)| - |S(x)∩S(y)|，其中S(x)是包含点x的区间集合。

1. 候选点筛选 #

最优的两个点一定是某个区间的端点（或者端点附近，因为在区间内部移动点，覆盖的区间数不会变化）。所以我们可以把所有区间的左、右端点收集起来，排序后作为候选点，这样候选点数量最多是2n个，完全可控。

2. 预处理关键统计量 #

我们需要先计算三个核心数组：

a. 单点覆盖数 count[p] #

对于每个候选点p，计算有多少个区间包含p。高效计算可以用差分法：

• 把所有区间的左端点a标记为+1，右端点b标记为-1（注意如果是开区间，p在(a,b)内才被覆盖，实际处理时直接用端点排序后计算前缀和即可，因为端点之间的区间覆盖数是恒定的）。
• 将所有标记点排序，遍历计算前缀和，就能得到每个候选点的count[p]。

b. 左区间数 left[p] #

对于候选点p，left[p]表示右端点 ≤ p的区间数量（这些区间完全在p的左侧，不会被p或任何大于p的点覆盖）。

c. 右区间数 right[p] #

对于候选点p，right[p]表示左端点 ≥ p的区间数量（这些区间完全在p的右侧，不会被p或任何小于p的点覆盖）。

这两个数组可以通过对区间按右端点、左端点排序后，用前缀/后缀和快速计算。

3. 寻找最优点对 #

对于任意两个点x < y，既不被x也不被y覆盖的区间数等于left[x] + right[y]（左侧区间+右侧区间）。因此，我们要最大化的覆盖总数就是：

总覆盖数 = n - (left[x] + right[y])

要让这个值最大，等价于找到x < y使得left[x] + right[y]最小。

怎么高效找这个最小值？可以预处理一个前缀最小值数组：

• 先对候选点按从小到大排序。
• 遍历候选点，维护到当前位置为止的left最小值min_left。
• 对于每个y，计算min_left + right[y]，记录所有结果中的最小值。

最后用n减去这个最小值，就是我们要的最大总和。

回到你给的例子：
候选点排序后是[1,2,3,4,5,6,7,8]，left[2]=0（没有区间右端点≤2），right[7]=0（没有区间左端点≥7），所以left[2]+right[7]=0，总覆盖数6-0=6，这就是选点2和7的最优结果。而选点4时，left[4]=1，加上right[7]=0得到1，总覆盖数6-1=5，确实比最优解小。

整个流程的时间复杂度是O(n log n)，主要来自排序步骤，完全符合竞赛题的时间要求。

内容的提问来源于stack exchange，提问作者Thomas