面试算法题：求可同行最大人数及区间优化思路问询

你的区间操作方向完全正确 #

你用差分数组+前缀和的思路没问题，先拆解下每一步的实际意义：

• 对每个人的偏好区间[low, high]，执行range[low]++和range[high+1]--，本质是在标记：从人数low开始，愿意接受该人数同行的人多了1个；从人数high+1开始，愿意接受的人少了1个。
• 计算前缀和后得到的prefix[k]，直接代表：当同行人数为k时，有多少人的偏好区间包含k（也就是愿意和k个人一起同行的总人数）。

后续推进步骤 #

我们的核心目标是找到最大的同行人数m，满足：能选出m个人，每个人都接受“和m个人同行”这个条件。换句话说，当同行人数定为m时，至少要有m个人愿意参与——也就是prefix[m] >= m（因为prefix[m]是愿意接受m的总人数，从里面挑m个就行）。

拿你的示例来说：
前缀和数组是[0, 3, 4, 3, 1, 0]，遍历k从1到4：

• k=1：3≥1 → 可行，但不是最大
• k=2：4≥2 → 可行
• k=3：3≥3 → 可行
• k=4：1<4 → 不可行
  所以最大的可行m就是3，和预期输出一致。

具体实现步骤：

1. 确定所有人偏好中的最大上限max_high（比如示例里的4）。
2. 遍历前缀和数组中1到max_high的所有位置。
3. 记录所有满足prefix[k] >= k的k值，取其中最大的那个。如果没有符合条件的k（比如所有人要求的最少人数都大于总人数n），返回0即可。

针对大数值范围的优化（当max_high极大时） #

如果peoplePreferences里的max_high特别大（比如达到1e9），用数组存差分数组会直接内存溢出，这时候可以用离散化+差分数组的方法优化：

1. 收集所有区间的端点：把每个人的low和high+1都收集起来，去重后排序得到有序列表points。
2. 用哈希表（或字典）代替数组做差分数组：对每个[low, high]，在哈希表中给low对应的值+1，high+1对应的值-1。
3. 按顺序遍历排序后的points，计算实时前缀和cnt，同时检查当前区间内的可行m：
   • 假设当前点是p，下一个点是q，当前愿意接受的人数是cnt。
   • 如果cnt >= p，那么在区间[p, min(q-1, cnt)]里，最大的可行m是min(q-1, cnt)，用这个值更新全局最大值。
4. 遍历结束后，全局最大值就是答案。

这种方法的时间复杂度是O(n log n)（主要来自排序端点），完全能处理大数值范围的场景。

总结 #

• 你的初始思路完全正确，只需要在计算前缀和后，遍历寻找最大的m满足prefix[m] >= m即可。
• 数值范围较小时，用数组实现差分数组，复杂度O(n + M)；数值范围极大时，用离散化优化，复杂度O(n log n)。

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