LeetCode732. 我的日程安排表 III

题目描述

本题目来自LeetCode上的『732.我的日程安排表 III』

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k次预订。

给你一些日程安排 [start, end) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree()初始化对象。
• int book(int start, int end) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例1：

输入：
[“MyCalendarThree”, “book”, “book”, “book”, “book”, “book”, “book”]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]

解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

题解1 - 差分数组

对于一个日程安排 [start, end)，计数 mp[start]++，表示从 start 开始的日程加一，计数 mp[end]--，表示日程在 end 结束，日程数减一。我们依次对 mp 进行累加，求出最大值即可。

代码

cpp

class MyCalendarThree {
private:
    map<int, int> mp;
public:
    MyCalendarThree() {

    }
    
    int book(int start, int end) {
        int ans = 0, temp = 0;
        ++mp[start];
        --mp[end];
        for (const auto& [_, cnt] : mp) {
            temp += cnt;
            ans = max(ans, temp);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n2)
• 空间复杂度：O(n)

题解2 - 线段树+懒标记+动态开点

由于本题是多次查询，且值域很大，所以需要『动态开点』。为了减少时间复杂度，可以使用『懒标记』。

直接套板子就行。

代码

cpp

class SegmentTree {
private:
    struct Node {
        int val, add;
        Node *l, *r;
        Node(): val(0), add(0), l(nullptr), r(nullptr) {}
    };
    static constexpr int N = 1e9;
    Node *root;
public:
    SegmentTree() {
        root = new Node();
    }

    void pushUp(Node* node) {
        node->val = max(node->l->val, node->r->val);
    }

    void pushDown(Node* node) {
        if (node->l == nullptr) {
            node->l = new Node();
        }
        if (node->r == nullptr) {
            node->r = new Node();
        }
        if (node->add == 0) {
            return;
        }
        node->l->val += node->add, node->l->add += node->add;
        node->r->val += node->add, node->r->add += node->add;
        node->add = 0;
    }

    void update(int lc, int rc, int l, int r, int v) {
        update(root, lc, rc, l, r, v);
    }

    void update(Node* node, int lc, int rc, int l, int r, int v) {
        if (l > r) {
            return;
        }
        if (l <= lc && rc <= r) {
            node->add += v;
            node->val += v;
            return;
        }
        pushDown(node);
        int mid = lc + ((rc - lc) >> 1);
        if (l <= mid) {
            update(node->l, lc, mid, l, r, v);
        }
        if (r > mid) {
            update(node->r, mid + 1, rc, l, r, v);
        }
        pushUp(node);
    }

    int query(int lc, int rc, int l, int r) {
        return query(root, lc, rc, l, r);
    }

    int query(Node* node, int lc, int rc, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (l <= lc && rc <= r) {
            return node->val;
        }
        pushDown(node);
        int mid = lc + ((rc - lc) >> 1);
        int res = 0;
        if (l <= mid) {
            res = query(node->l, lc, mid, l, r);
        }
        if (r > mid) {
            res = max(res, query(node->r, mid + 1, rc, l, r));
        }
        return res;
    }
};
class MyCalendarThree {
private:
    SegmentTree *tree;
public:
    MyCalendarThree() {
        tree = new SegmentTree();
    }
    
    int book(int start, int end) {
        tree->update(0, 1e9, start, end - 1, 1);
        return tree->query(0, 1e9, 0, 1e9);
    }
};

复杂度分析

设 m 为日程安排的数量，N 为线段树最大的节点数，固定为 1e9

• 时间复杂度：因为有懒标记，线段树的插入和查询都是 O(logN)，总复杂度为 O(mlogN)

• 空间复杂度：每次最多开辟 O(logN) 的空间，总复杂度为 O(mlogN)