数据结构与算法 / 系统课时

区间调度问题

区间调度问题

区间调度要在单个资源上安排尽可能多的互不重叠任务。本课将任务建模为半开区间,使用“优先选择最早结束区间”的贪心策略,并通过交换论证说明它为何优于最早开始或区间最短等直觉方案。

学习目标

  • 将会议或任务抽象为带开始、结束时间的半开区间
  • 使用结束时间升序排序选择最多兼容区间
  • 正确处理边界语义、输入校验和复杂度

问题建模与选择规则

使用半开区间 [start, end) 表示任务占用时间,结束时刻不属于当前区间。因此前一区间的结束时间等于后一区间的开始时间时,两者可以连续安排,兼容条件是 next.start >= lastEnd。

算法先按结束时间升序排序,再从左到右扫描。遇到与已选集合兼容的区间就选择它,并把 lastEnd 更新为该区间的结束时间。选择越早结束的任务,留给后续任务的可用时间越多。

区间调度的最早结束选择

正确性:交换第一个区间

设某个最优解的第一个区间是 O,贪心算法选择结束时间最早的区间 G。由于 G.end <= O.end,将最优解中的 O 替换为 G 后,原本能排在 O 之后的区间仍可排在 G 之后,因此区间数量不会减少。

这说明至少存在一个以 G 开头的最优解。选择 G 后,剩余问题变为“从 G.end 之后继续选择最多兼容区间”,仍然是同类型问题。最早开始可能选中持续很久的任务,区间最短也可能占据时间轴中部,二者都不能保证给后续任务留下最大空间。

主示例:输出最大兼容集合

下面的 Java 17 程序复制输入列表后排序,并校验每个区间满足 start <= end。相同结束时间再按开始时间和名称排序,使结果稳定、便于测试。

java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class IntervalSchedulingDemo {

    private record Interval(String name, int start, int end) {
    }

    public static void main(String[] args) {
        List<Interval> intervals = List.of(
            new Interval("A", 1, 4),
            new Interval("B", 3, 5),
            new Interval("C", 0, 6),
            new Interval("D", 5, 7),
            new Interval("E", 3, 9),
            new Interval("F", 5, 9),
            new Interval("G", 6, 10),
            new Interval("H", 8, 11),
            new Interval("I", 8, 12),
            new Interval("J", 2, 14),
            new Interval("K", 12, 16)
        );

        List<Interval> selected = selectMaximumCompatible(intervals);
        System.out.println("最多可安排区间数: " + selected.size());
        for (Interval interval : selected) {
            System.out.printf(
                "%s: [%d, %d)%n",
                interval.name(),
                interval.start(),
                interval.end()
            );
        }
    }

    private static List<Interval> selectMaximumCompatible(
        List<Interval> input
    ) {
        List<Interval> intervals = new ArrayList<>(input);
        for (Interval interval : intervals) {
            if (interval.start() > interval.end()) {
                throw new IllegalArgumentException(
                    "区间开始时间不能晚于结束时间"
                );
            }
        }

        intervals.sort(
            Comparator.comparingInt(Interval::end)
                .thenComparingInt(Interval::start)
                .thenComparing(Interval::name)
        );

        List<Interval> selected = new ArrayList<>();
        int lastEnd = Integer.MIN_VALUE;

        for (Interval interval : intervals) {
            if (interval.start() >= lastEnd) {
                selected.add(interval);
                lastEnd = interval.end();
            }
        }
        return selected;
    }
}

预期输出:

text
最多可安排区间数: 4
A: [1, 4)
D: [5, 7)
H: [8, 11)
K: [12, 16)

输出集合两两兼容。相同输入若只需要数量,可以不保存 selected,只维护计数器和 lastEnd。

边界与复杂度

空列表返回空结果。零长度区间 [t, t) 在半开区间语义下不占用时间,可以与结束或开始于 t 的区间兼容;业务若不允许零长度任务,应在校验阶段改为要求 start < end。

排序时间复杂度为 O(n log n),扫描为 O(n),总时间复杂度为 O(n log n)。结果列表最多保存 n 个区间,额外空间为 O(n)。若输入已经按结束时间排序,核心扫描只需 O(n)。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

区间调度问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通