731. 我的日程安排表 II

  • 线段树
  • 哈希

题干

见上面的链接

解法

两种解法的题解都是来自于官方题解

线段树-OI Wiki

线段树

  • 线段树3个主要的操作：

    • 建树
    • 查询区间
    • 修改区间

  • 对于本题

    • 建树：

      开辟1e9的过于耗费空间，所以用了动态线段树，即使用unordered_map，而不是数组

      又因为初始的值都是0，所以不需要建树的过程

    • 查询区间：

      这是一个维护最大值的线段树，且查询的时候只需要查询全局的最大值，不用查询子区间的最大值，所以每次查询都是固定的tree[1].first

    • 修改区间：

      主要参考下面代码中的update()函数

      tree[idx].second即为lazy标记的值，表示子结点未更新的值

  • 代码：

    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
    class MyCalendarTwo {
    public:
        MyCalendarTwo() {

        }
    //线段树：建树-查询区间-修改区间
    //开辟1e9的过于耗费空间，所以用了动态线段树，使用unordered_map，而不是数组
    //又因为初始的值都是0，所以不需要建树的过程
    //tree[idx].second即为lazy标记的值，表示子结点未更新的值
    //这是一个维护最大值的线段树，且查询的时候只需要查询全局的最大值，不用查询子区间的最大值，所以每次查询都是固定的tree[1].first
        void update(int start, int end, int val, int l, int r, int idx) //维护区间[start,end]的值的子函数
        {
            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);
            }
        }

        bool book(int start, int end) //更新区间[start,end]的值
        {            
            update(start, end - 1, 1, 0, 1e9, 1);
            if (tree[1].first > 2) //tree[1].first保存的即为每一天的日程个数的最大值
            {
                update(start, end - 1, -1, 0, 1e9, 1);
                return false;
            }
            return true;
        }
    private:
        unordered_map<int, pair<int, int>> tree;
    };

哈希

正常来讲，差分数组要建1e9很费空间，维护起来也很耗时

换个思路，用map维护差分数组

  • 刚好本题要保证的是【最大值<3】，只需要判断是否出现这种情况，不用知道每个区间各自的值

    思路见代码，比较好懂

  • 代码：

    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
    class MyCalendarTwo {
    public:
        MyCalendarTwo() {

        }

        bool book(int start, int end) {
            int ans = 0;
            int maxBook = 0;
            cnt[start]++;
            cnt[end]--;
            for (auto &[_, freq] : cnt) {
                maxBook += freq;
                ans = max(maxBook, ans);
                if (maxBook > 2) {
                    cnt[start]--;
                    cnt[end]++;
                    return false;
                }
            }
            return true;
        }
    private:
        map<int, int> cnt;
    };