Hard

题目描述

当 k 个事件有一些非空交集时（即有一些时间对所有 k 个事件都是共同的），就会产生一个 k 次预订。

给你一些事件 [startTime, endTime)，在每个给定的事件之后，返回一个整数 k，表示所有先前事件中的最大 k 次预订。

实现 MyCalendarThree 类：

  • MyCalendarThree() 初始化对象。
  • int book(int startTime, int endTime) 返回一个整数 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
myCalendarThree.book(50, 60); // 返回 1
myCalendarThree.book(10, 40); // 返回 2
myCalendarThree.book(5, 15); // 返回 3
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

约束条件：

  • 0 <= startTime < endTime <= 10^9
  • 最多调用 400 次 book。

解题思路

这道题要求我们维护一个日历系统，并返回任意时刻最大的重叠次数。我们可以使用扫描线算法来解决这个问题。

核心思路：

  1. 事件拆分：将每个时间区间 [start, end) 拆分为两个事件：

    • 在 start 时刻，事件开始（+1）
    • 在 end 时刻，事件结束（-1）

  2. 有序映射：使用有序映射（如 TreeMap/SortedDict）来存储每个时间点的事件变化值。当新增一个区间时，在 start 位置 +1，在 end 位置 -1。

  3. 实时计算最大值：每次插入新区间后，按时间顺序遍历所有事件点，累加变化值来计算当前重叠数，并维护历史最大值。

时间复杂度优化：

  • 插入操作：O(log n)
  • 计算最大重叠：O(n)，其中 n 是不同时间点的数量

这种方法的优势在于能够高效地处理大范围的时间值（最大 10^9），而且实现相对简单。虽然每次 book 操作需要重新计算最大值，但由于最多只有 400 次调用，总体性能是可以接受的。

推荐解法： 扫描线 + 有序映射，代码简洁且易于理解。

代码实现

class MyCalendarThree {
private:
    map<int, int> timeline;
    
public:
    MyCalendarThree() {
        
    }
    
    int book(int startTime, int endTime) {
        timeline[startTime]++;
        timeline[endTime]--;
        
        int maxBooking = 0;
        int currentBooking = 0;
        
        for (auto& event : timeline) {
            currentBooking += event.second;
            maxBooking = max(maxBooking, currentBooking);
        }
        
        return maxBooking;
    }
};

class MyCalendarThree:

    def __init__(self):
        self.timeline = {}

    def book(self, startTime: int, endTime: int) -> int:
        self.timeline[startTime] = self.timeline.get(startTime, 0) + 1
        self.timeline[endTime] = self.timeline.get(endTime, 0) - 1
        
        max_booking = 0
        current_booking = 0
        
        for time in sorted(self.timeline.keys()):
            current_booking += self.timeline[time]
            max_booking = max(max_booking, current_booking)
        
        return max_booking

public class MyCalendarThree {
    private SortedDictionary<int, int> timeline;

    public MyCalendarThree() {
        timeline = new SortedDictionary<int, int>();
    }
    
    public int Book(int startTime, int endTime) {
        if (timeline.ContainsKey(startTime)) {
            timeline[startTime]++;
        } else {
            timeline[startTime] = 1;
        }
        
        if (timeline.ContainsKey(endTime)) {
            timeline[endTime]--;
        } else {
            timeline[endTime] = -1;
        }
        
        int maxBooking = 0;
        int currentBooking = 0;
        
        foreach (var kvp in timeline) {
            currentBooking += kvp.Value;
            maxBooking = Math.Max(maxBooking, currentBooking);
        }
        
        return maxBooking;
    }
}

var MyCalendarThree = function() {
    this.timeline = new Map();
};

MyCalendarThree.prototype.book = function(startTime, endTime) {
    this.timeline.set(startTime, (this.timeline.get(startTime) || 0) + 1);
    this.timeline.set(endTime, (this.timeline.get(endTime) || 0) - 1);
    
    let maxBooking = 0;
    let currentBooking = 0;
    
    const sortedTimes = Array.from(this.timeline.keys()).sort((a, b) => a - b);
    
    for (const time of sortedTimes) {
        currentBooking += this.timeline.get(time);
        maxBooking = Math.max(maxBooking, currentBooking);
    }
    
    return maxBooking;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
扫描线 + 有序映射O(n log n + n)O(n)

说明：

  • 时间复杂度：每次 book 操作中，插入两个时间点需要 O(log n)，遍历计算最大值需要 O(n)，其中 n 是不同时间点的数量
  • 空间复杂度：O(n)，用于存储时间线映射，最多存储 2×400 = 800 个时间点

相关题目