区间划分
把所有区间分配到最少机器,使同一机器上的区间不重叠;答案等于最大重叠深度,按左端点排序并用小根堆维护结束时间。标签 贪心 / 区间 / 堆 / 调度
题目描述
给定 个区间 。把所有区间分配到尽量少的机器上,使同一台机器上的区间两两不重叠。
端点相接视为相容。
题解
按左端点 升序排序。维护一个小根堆,存放每台机器最后一个区间的右端点。
依次处理每个区间 :
- 若堆顶不超过 ,说明存在已经空闲的机器,弹出最早空闲的结束时间;
- 否则必须新开一台机器;
- 把 压入堆。
堆的最大大小就是最少机器数。
为什么最优:任意时刻重叠的区间必须使用不同机器,所以机器数至少是最大重叠深度。若当前区间无法复用已有机器,说明堆中所有机器最后区间的右端点都大于 ,这些区间都与当前区间重叠;加上当前区间,重叠数又增加一,所以新开机器是必要的。能复用时选择最早结束的机器,不会比选其他机器更差。
复杂度
排序为 ,每个区间至多进出堆一次,堆操作为 。总时间为 ,空间为 。