如何将区间集合划分到最少数量的无重叠bins/桶中

问题本质 #

你要解决的是经典的区间图着色问题，理论上可证明：最少需要的桶数，等于给定区间集合中同一时间点重叠的区间的最大数量。

你的猜想验证 #

按区间长度从大到小排序处理的猜想不成立，无法保证得到最少桶数，可参考以下反例：
假设有4个区间：

• A: [0, 10]，长度10
• D: [1.5, 3.5]，长度2
• B: [1, 2]，长度1
• C: [3, 4]，长度1
  按长度降序处理的结果：

1. A放入桶1，桶1最后结束点为10
2. D和桶1重叠，新建桶2，桶2最后结束点为3.5
3. B和桶1、桶2都重叠，新建桶3，桶3最后结束点为2
4. C和桶1、桶2都重叠，新建桶4，桶4最后结束点为4
   最终用了4个桶，但该场景下最少仅需要3个桶（桶1放A；桶2放B、C；桶3放D），显然按长度降序的策略不是最优。

最优实现方案 #

要保证得到最少桶数，且时间效率最优，可采用以下方案：

处理顺序 #

所有区间按起始点从小到大排序，起始点相同的按结束点从小到大排序。

实现逻辑 #

1. 维护一个最小堆，存储每个桶当前最后一个区间的结束点
2. 遍历排序后的所有区间，对每个区间[cur_start, cur_end]：
   • 取堆顶的最小结束点，如果该值 ≤ cur_start，说明这个桶可以放下当前区间，弹出堆顶，将cur_end压入堆
   • 如果堆顶的结束点 > cur_start，说明所有现有桶的最后区间都和当前区间重叠，直接将cur_end压入堆，即新建一个桶
3. 最终堆的大小就是最少需要的桶数

复杂度 #

整体时间复杂度为O(n log n)，其中n为区间总数，是该问题的理论最优时间复杂度。

原有问题说明 #

你之前处理顺序不同结果不同的核心原因是没有采用保证最优的排序策略，随机顺序处理时很容易出现区间分配不合理、被迫额外新建桶的情况。

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