0732：我的日程安排表 III（★★）

Ian

2017-01-01 约 625 字预计阅读 2 分钟次阅读

力扣第 732 题

题目

当 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

提示：

0 <= startTime < endTime <= 10⁹
每个测试用例，调用 book 函数最多不超过 400次

相似问题：

分析

#1

查询次数较小，可以直接用差分。

1
2
3
4
5
6
7
8
9


class MyCalendarThree:
    def __init__(self):
        self.d = defaultdict(int)

    def book(self, start: int, end: int) -> int:
        d = self.d
        d[start] += 1
        d[end] -= 1
        return max(accumulate(d[x] for x in sorted(d)))

674 ms

#2

更通用的是线段树，区间修改并查询。

解答

 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


class MyCalendarThree:

    def __init__(self):
        self.t = defaultdict(int)
        self.f = defaultdict(int)
    
    def do(self,o,x):
        self.t[o] += x
        self.f[o] += x
    
    def down(self,o):
        if self.f[o]!=0:
            self.do(o*2,self.f[o])
            self.do(o*2+1,self.f[o])
            self.f[o] = 0

    def update(self,a,b,x,o,l,r):
        if a<=l and r<=b:
            self.do(o,x)
            return 
        m = (l+r)//2
        self.down(o)
        if a<=m: self.update(a,b,x,o*2,l,m)
        if m<b: self.update(a,b,x,o*2+1,m+1,r)
        self.t[o] = max(self.t[o*2],self.t[o*2+1])

    def book(self, startTime: int, endTime: int) -> int:
        self.update(startTime,endTime-1,1,1,0,10**9)
        return self.t[1]

841 ms

目录

0732：我的日程安排表 III（★★）

题目

分析

#1

#2

解答