题解

class MyCalendarTwo {
public:
    MyCalendarTwo() { 
    }

    // 更新线段树的某个区间
    void update(int start, int end, int val, int l, int r, int idx) {
        if (r < start || end < l) return; // 当前区间与更新区间无交集，直接返回

        if (start <= l && r <= end) {
            // 当前区间完全包含在更新区间内，更新值和懒标记
            tree[idx].first += val;
            tree[idx].second += val;
        } else {
            // 当前区间部分包含在更新区间内，递归更新左右子树
            int mid = (l + r) >> 1;
            update(start, end, val, l, mid, 2 * idx);
            update(start, end, val, mid + 1, r, 2 * idx + 1);

            // 更新当前节点的值为懒标记加上左右子树的最大值
            tree[idx].first = tree[idx].second + max(tree[2 * idx].first, tree[2 * idx + 1].first);
        }
    }

    // 尝试预订区间 [start, end)
    bool book(int start, int end) {            
        update(start, end - 1, 1, 0, 1e9, 1); // 尝试预订，区间值 +1

        if (tree[1].first > 2) {
            // 如果根节点值 > 2，说明有三次重叠，撤销预订
            update(start, end - 1, -1, 0, 1e9, 1);
            return false; // 预订失败
        }
        return true; // 预订成功
    }

private:
    // 线段树节点存储：first 是节点值，second 是懒标记
    unordered_map<int, pair<int, int>> tree;
};

思路

线段树 + 懒标记

1. ​数据结构 ​：
   • 使用线段树维护每个时间区间的预订次数。
   • 每个节点存储：
     • first：当前区间的最大值（最大重叠次数）。
     • second：懒标记，表示待传递的更新值。
2. ​更新操作（update） ​：
   • 将区间 [start, end) 的值增加 val（1 表示预订，-1 表示撤销）。
   • 如果当前节点区间完全包含在 [start, end) 内，更新值和懒标记。
   • 否则，递归更新左右子节点，并更新当前节点的值为懒标记加上左右子树的最大值。
3. ​预订操作（book） ：
   • 尝试预订：调用 update，将区间 [start, end - 1] 的值增加 1。
   • 检查根节点的值：
     • 如果 tree[1].first > 2，说明有三次重叠，撤销预订并返回 false。
     • 否则，返回 true。
4. ​懒标记的作用​ ：
   • 懒标记的含义：懒标记（second）表示当前节点的实际累加值，即该区间内所有时间点的重叠预订次数的增量。节点值（first）表示当前区间的最大值，即该区间及其子区间内某个时间点的最大重叠预订次数。
   • 为什么需要懒标记：在更新父节点时，如果直接对 first 进行自增，会导致父节点的值错误地累加多次，无法正确反映子区间的最大值。通过懒标记，将实际累加值（second）与子节点的最大值（first）分开维护，确保父节点的值正确更新。