自学内容网 自学内容网

【数据结构-线段树】【差分】力扣732. 我的日程安排表 III

当 k 个日程存在一些非空交集时(即, k 个日程包含了一些相同时间),就会产生 k 次预订。

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

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

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

在这里插入图片描述

示例:
输入:
[“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

线段树

class MyCalendarThree {
public:
    unordered_map<int, pair<int, int>> tree;

    MyCalendarThree() {

    }
    
    void update(int start, int end, int l, int r, int idx) {
        if (r < start || end < l) {
            return;
        } 
        if (start <= l && r <= end) {
            tree[idx].first++;
            tree[idx].second++;
        } else {
            int mid = (l + r) >> 1;
            update(start, end, l, mid, 2 * idx);
            update(start, end, mid + 1, r, 2 * idx + 1);
            tree[idx].first = tree[idx].second + max(tree[2 * idx].first, tree[2 * idx + 1].first);
        }
    }

    int book(int start, int end) {            
        update(start, end - 1, 0, 1e9, 1);
        return tree[1].first;
    }
};

在这里插入图片描述
在这里插入图片描述
当需要频繁查询的时候,线段树效率较高,但该题要频繁区间更新,且只在最后求一次结果,选择差分数组效率较高。
该线段树的算法涉及到了懒标记,通过懒标记,当某个线段树节点区间在查询区间范围内,可以使懒标记+1,然后不用继续递归下面的子节点。
还有一点需要注意的是,该线段树的索引idx从1开始,所以某个节点的子节点的索引为2idx和2idx+1。倘若从0开始索引,那么就是2idx+1和2idx+2。

差分

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

     }
    
    int book(int startTime, int endTime) {
        diff[startTime]++;
        diff[endTime]--;

        int s = 0, ans = 0;
        for(auto& [_, d] : diff){
            s += d;
            ans = max(ans, s);
        }
        return ans;
    }
};

时间复杂度:O(n^2 ),其中 n 为日程安排的数量。每次求的最大的预定需要遍历所有的日程安排。

空间复杂度:O(n),其中 n 为日程安排的数量。需要空间存储所有的日程安排计数,需要的空间为 O(n)。

使用了 map<int, int> 来模拟差分数组的效果,记录每个时间点的变化量。然后通过累加这些变化量,计算得到最大重叠次数。


原文地址:https://blog.csdn.net/sjsjs11/article/details/142341320

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!