日程安排表（区间重叠检测）

我的日程安排表 I（LeetCode 729）

添加事件 [start, end)，若与已有事件重叠则拒绝，返回 false。

TreeMap 解法（工业级推荐）

class MyCalendar {
    private TreeMap<Integer, Integer> calendar = new TreeMap<>();

    public boolean book(int start, int end) {
        // 找到 start 左边最近的事件和右边最近的事件
        Map.Entry<Integer, Integer> prev = calendar.floorEntry(start);
        Map.Entry<Integer, Integer> next = calendar.ceilingEntry(start);
        // 新事件不与 prev 重叠（prev.end <= start）
        // 不与 next 重叠（end <= next.start）
        if ((prev == null || prev.getValue() <= start) &&
            (next == null || end <= next.getKey())) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }
}

时间：O(log n)，空间 O(n)。

我的日程安排表 II（LeetCode 731）

允许最多双重预订，三重重叠才拒绝。

维护两个集合：booked（单次）和 doubleBooked（双重）。

class MyCalendarTwo {
    private List<int[]> booked = new ArrayList<>();
    private List<int[]> doubleBooked = new ArrayList<>();

    public boolean book(int start, int end) {
        // 检查是否与已双重预订的区间重叠（会变成三重）
        for (int[] d : doubleBooked) {
            if (start < d[1] && end > d[0]) return false;
        }
        // 计算与已预订区间的交集，加入双重预订
        for (int[] b : booked) {
            int lo = Math.max(start, b[0]);
            int hi = Math.min(end, b[1]);
            if (lo < hi) doubleBooked.add(new int[]{lo, hi});
        }
        booked.add(new int[]{start, end});
        return true;
    }
}

我的日程安排表 III（LeetCode 732）

任意时刻最多 k 重预订，返回当前最大重叠数。

差分数组（Difference Array）

class MyCalendarThree {
    private TreeMap<Integer, Integer> diff = new TreeMap<>();

    public int book(int start, int end) {
        diff.merge(start, 1, Integer::sum);
        diff.merge(end, -1, Integer::sum);
        int max = 0, cur = 0;
        for (int v : diff.values()) {
            cur += v;
            max = Math.max(max, cur);
        }
        return max;
    }
}

时间：O(n) 遍历，O(log n) 更新，总体 O(n²)；线段树可优化到 O(n log n)。

区间设计总结