【Leetcode】732. 我的日程安排表 III

题目

题目链接🔗
当 $k$ 个日程存在一些非空交集时（即, $k$ 个日程包含了一些相同时间），就会产生 $k$ 次预订。

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

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

$MyCalendarThree()$ 初始化对象。
$intbook(intstartTime,intendTime)$ 返回一个整数 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

提示：

1. $0\le startTime<endTime\le 10^9$
   每个测试用例，调用 $book$ 函数最多不超过 $400$次

思路

当 $k$ 个日程存在一些非空交集时（即, $k$ 个日程包含了一些相同时间），就会产生 $k$ 次预订。那么可以转化为：理解成start时刻预定了一人，可能后面还会又预定了一人，end时刻离开，求预定的人数最大值，预定时间为整数，可以使用差分来实现

代码

class MyCalendarThree {
public:
    map<int,int> m;
    MyCalendarThree() {
    }
    
    int book(int startTime, int endTime) {
        // 在 startTime 处增加一个活动
        ++m[startTime];
        // 在 endTime 处减少一个活动
        --m[endTime];

        int sum = 0; // 当前重叠的活动数
        int maxOverlap = 0; // 最大重叠的活动数

        // 遍历时间点，计算最大重叠数
        for (map<int, int>::iterator it = m.begin(); it != m.end(); ++it) {
            sum += it->second;
            if (sum > maxOverlap) {
                maxOverlap = sum;
            }
        }

        return maxOverlap;
    }
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(startTime,endTime);
 */

复杂度分析

时间复杂度

每次调用 $book$ 方法时：
在有序映射 $m$ 中插入或更新两个键值对（$startTime$ 和 $endTime$），每次操作的时间复杂度为 $O(logN)$，其中 $N$ 是当前映射中的键的数量。
遍历映射 $m$ 以计算最大重叠数，时间复杂度为 $O(N)$

空间复杂度

映射 $m$ 中存储了所有的时间点，每个时间点对应一个活动的开始或结束。
在最坏情况下，可能每个活动都有唯一的开始和结束时间点，因此空间复杂度为 $O(N)$

结果

总结

使用差分数组可以高效地对数组的连续区间进行加法操作，避免了对每个区间内的元素逐一更新。