区间划分

把所有区间分配到最少机器,使同一机器上的区间不重叠;答案等于最大重叠深度,按左端点排序并用小根堆维护结束时间。

标签 贪心 / 区间 / 堆 / 调度

题目描述

给定 𝑛 个区间 [𝑙𝑖,𝑟𝑖]。把所有区间分配到尽量少的机器上,使同一台机器上的区间两两不重叠。

端点相接视为相容。

题解

按左端点 𝑙𝑖 升序排序。维护一个小根堆,存放每台机器最后一个区间的右端点。

依次处理每个区间 [𝑙𝑖,𝑟𝑖]:

  • 若堆顶不超过 𝑙𝑖,说明存在已经空闲的机器,弹出最早空闲的结束时间;
  • 否则必须新开一台机器;
  • 把 𝑟𝑖 压入堆。

堆的最大大小就是最少机器数。

为什么最优:任意时刻重叠的区间必须使用不同机器,所以机器数至少是最大重叠深度。若当前区间无法复用已有机器,说明堆中所有机器最后区间的右端点都大于 𝑙𝑖,这些区间都与当前区间重叠;加上当前区间,重叠数又增加一,所以新开机器是必要的。能复用时选择最早结束的机器,不会比选其他机器更差。

复杂度

排序为 𝑂(𝑛log𝑛),每个区间至多进出堆一次,堆操作为 𝑂(𝑛log𝑛)。总时间为 𝑂(𝑛log𝑛),空间为 𝑂(𝑛)。

参考

源码位置