力扣 731. 我的日程安排表 II

题目来源：https://leetcode.cn/problems/my-calendar-ii/

大致题意：
设计一个日程类 MyCalendar，包含以下功能：

• 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。
每次调用 book 方法会产生一个日程，如果发生了三重预定则返回 false，并取消该日程，否则添加该日程

思路

可以直接使用差分数组解题，每次插入日程即为 [start, end - 1] 的区间内值 +1，对于差分数组来说直接在 start 位置 +1，end 位置 -1 即可。这里不赘述差分解法，主要为线段树解法

对于这类对区间整理进行增减，或者最值、统计操作，使用线段树是比较好的。因为线段树的区间操作中，增删、查的时间复杂度都为 O(log n)

唯一的问题是，线段树需要开辟 4n 的空间，该题的数据范围为 0~10⁹，直接申请空间过于浪费，也会导致内存超限，所以需要使用线段树动态开点，即需要某个节点时才创建该节点

该题主要是实现 book 方法，可以先实现一个 update 方法用于更新线段树，每次预定时，在线段树中更新给定区间的值 +1，如果更新后区间的最大值大于 2，也就代表产生了三重预定，此时回滚操作，即更新区间的值 -1，并返回 false；否则直接返回 true

动态开点的线段树可以使用哈希表存，key 为节点编号，value 为包含两个元素的数组，数组第一个元素为当前节点区间内的最大值，第二个元素为懒标记，即当前区间的最小值，也是当前区间整体被预定的次数（节点全部被预定）

具体看代码：

public class MyCalendarTwo {
    // 维护线段树节点与对应值
    // key 为节点编号，值为 int 数组，第一个元素表示区间内最大值，第二个元素为懒标记，表示区间全覆盖的值（类似区间最小值）
    Map<Integer, int[]> tree;
    int BORDER;

    public MyCalendarTwo() {
        BORDER = (int) 1e9;
        tree = new HashMap<>();
    }

    public boolean book(int start, int end) {
        // 先放入该区间
        update(start, end - 1, 1, 0, BORDER, 1);
        // 如果更新后区间内最大值大于 2，表示产生了三重预定
        if (tree.get(1)[0] > 2) {
            // 删除该区间
            update(start, end - 1, -1, 0, BORDER, 1);
            return false;
        }
        return true;
    }

    /**
     * 区间 [start, end] 内的值加上 val
     * @param start
     * @param end
     * @param val
     * @param l
     * @param r
     * @param idx
     */
    public void update(int start, int end, int val, int l, int r, int idx) {
        // 如果该节点还未创建，则新建
        tree.putIfAbsent(idx, new int[2]);
        // 如果更新区间不在线段树节点包含范围内，直接返回
        if (start > r || end < l) {
            return;
        }
        // 更新区间包含了线段树节点的所有范围，更新该线段树节点的值
        if (start <= l && r <= end) {
            tree.get(idx)[0] += val;
            tree.get(idx)[1] += val;
            return;
        }
        int mid = (l + r) >> 1;
        // 递归更新
        update(start, end, val, l, mid, idx * 2);
        update(start, end, val, mid + 1, r, idx * 2 + 1);
        // 更新区间最大值
        // 该最大值即为左右子节点的最大值（左右子节点区间内最大值）加上当前节点的懒标记值（区间全覆盖增加的值）
        tree.get(idx)[0] = tree.get(idx)[1] + Math.max(tree.get(idx * 2)[0], tree.get(idx * 2 + 1)[0]);
    }

    public static void main(String[] args) {
        MyCalendarTwo_SegmentTree tree = new MyCalendarTwo_SegmentTree();
        System.out.println(tree.book(24, 40));
        System.out.println(tree.book(43, 50));
        System.out.println(tree.book(27, 43));
        System.out.println(tree.book(5, 21));
        System.out.println(tree.book(30, 40));
        System.out.println(tree.book(14, 29));
        System.out.println(tree.book(3, 19));
        System.out.println(tree.book(3, 14));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66