区间分配问题（Interval Partitioning Problem） 题目描述 区间分配问题是指给定一组区间（每个区间有开始时间和结束时间），目标是将所有区间分配到尽可能少的资源（例如会议室、机器等）上，使得分配到同一资源上的区间互不重叠。换句话说，就是找出最小的资源数，使得所有区间都能被安排而不发生冲突。 解题过程 问题分析 输入：一组区间 [start_i, end_i] ，其中 start_i 和 end_i 分别表示第 i 个区间的开始和结束时间。 输出：最小的资源数量 k ，使得所有区间可以分配到 k 个资源上，且同一资源上的区间互不重叠。 关键点：当多个区间在时间上重叠时，它们必须被分配到不同的资源。因此，最小资源数等于最大重叠区间数（即在某个时间点同时进行的区间数量的最大值）。 贪心策略 核心思想：按照区间的开始时间排序，然后按顺序分配资源。每次分配时，将当前区间分配给第一个可用的资源（即该资源上最后一个区间的结束时间早于当前区间的开始时间）。如果当前区间与所有已分配资源的最后一个区间都重叠，则必须开辟一个新资源。 为什么贪心有效？因为按开始时间排序后，我们总是优先处理更早开始的区间，从而避免后序区间因资源不足而无法分配。 算法步骤 步骤1 ：将所有区间按开始时间升序排序。 步骤2 ：维护一个最小堆（或优先队列），用于记录每个资源上最后一个区间的结束时间。堆的大小即为当前已使用的资源数。 步骤3 ：遍历排序后的区间： 若堆为空（尚无资源），直接分配一个新资源，并将当前区间的结束时间加入堆。 若堆非空，检查堆顶（最早结束时间）： 若堆顶的结束时间 ≤ 当前区间的开始时间，说明该资源可用。将堆顶弹出，将当前区间的结束时间加入堆（相当于复用该资源）。 否则，当前区间与所有现有资源冲突，必须分配新资源（将当前结束时间加入堆）。 步骤4 ：遍历完成后，堆的大小即为所需的最小资源数。 示例演示 假设区间为 [[1, 4], [2, 5], [3, 6], [5, 7]] ： 排序后： [[1, 4], [2, 5], [3, 6], [5, 7]] 。 初始化堆 [] 。 处理 [1, 4] ：堆为空，分配资源1，堆变为 [4] 。 处理 [2, 5] ：堆顶 4 > 开始时间 2 ，冲突，分配资源2，堆变为 [4, 5] 。 处理 [3, 6] ：堆顶 4 > 开始时间 3 ，冲突，分配资源3，堆变为 [4, 5, 6] 。 处理 [5, 7] ：堆顶 4 ≤ 开始时间 5 ，复用资源1，弹出 4 加入 7 ，堆变为 [5, 6, 7] 。 最终堆大小 = 3，最小资源数为3。 复杂度分析 排序耗时 O(n log n) ，其中 n 为区间数量。 堆操作每次 O(log k) ， k 为资源数（最坏情况 k ≤ n ），总操作 O(n log n) 。 总复杂度： O(n log n) 。 关键理解点 最小堆的作用是动态跟踪最早可用的资源，避免每次检查所有资源。 该问题等价于求最大区间重叠数（可通过扫描线算法验证），但贪心法直接给出了分配方案。