当前位置：首页 > article >正文

LeetCode 0732.我的日程安排表 III：线段树

article 2025/1/7 18:26:34

【LetMeFly】732.我的日程安排表 III：线段树

力扣题目链接：https://leetcode.cn/problems/my-calendar-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

提示：

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

解题方法：线段树

离散化线段树，tree记录区间最大值，lazy懒标记区间的累加次数。

时间复杂度 $O(n\log C)$ ，线段树最大深度为 $\log C$ ，其中 $C=10^9$
空间复杂度 $O(n\log C)$ ，每次预定最多新增 $\log C$ 个节点

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-01-05 21:26:02
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-05 21:33:46
 */
class MyCalendarThree {
private:
    unordered_map<int, int> tree, lazy;

    void update(int start, int end, int index, int l, int r) {
        if (start > r || l > end) {
            return;
        }
        if (l >= start && r <= end) {
            tree[index]++;
            lazy[index]++;
        } else {
            int mid = (l + r) >> 1;
            update(start, end, index * 2 + 1, l, mid);
            update(start, end, index * 2 + 2, mid + 1, r);
            tree[index] = lazy[index] + max(tree[index * 2 + 1], tree[index * 2 + 2]);
        }
    }
public:
    MyCalendarThree() {}
    
    int book(int startTime, int endTime) {
        update(startTime, endTime - 1, 0, 0, 1000000000);
        return tree[0];
    }
};

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

Python

'''
Author: LetMeFly
Date: 2025-01-05 21:34:19
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-05 21:38:20
'''
from collections import defaultdict

class MyCalendarThree:

    def __init__(self):
        self.tree = defaultdict(int)
        self.lazy = defaultdict(int)

    def update(self, start: int, end: int, index: int, l: int, r: int) -> None:
        if l > end or start > r:
            return
        if start <= l and r <= end:
            self.tree[index] += 1
            self.lazy[index] += 1
        else:
            mid = (l + r) >> 1
            self.update(start, end, index * 2 + 1, l, mid)
            self.update(start, end, index * 2 + 2, mid + 1, r)
            self.tree[index] = self.lazy[index] + max(self.tree[index * 2 + 1], self.tree[index * 2 + 2])

    def book(self, startTime: int, endTime: int) -> int:
        self.update(startTime, endTime - 1, 0, 0, 1000000000)
        return self.tree[0]


# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-01-05 21:39:30
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-05 21:44:12
 */
import java.util.HashMap;

class MyCalendarThree {
    private HashMap<Integer, Integer> tree, lazy;

    private void update(int start, int end, int index, int l, int r) {
        if (l > end || start > r) {
            return;
        }
        if (l >= start && r <= end) {
            tree.put(index, tree.getOrDefault(index, 0) + 1);
            lazy.put(index, lazy.getOrDefault(index, 0) + 1);
        } else {
            int mid = (l + r) >> 1;
            update(start, end, index * 2 + 1, l, mid);
            update(start, end, index * 2 + 2, mid + 1, r);
            tree.put(index, lazy.getOrDefault(index, 0) + Math.max(tree.getOrDefault(index * 2 + 1, 0), tree.getOrDefault(index * 2 + 2, 0)));
        }
    }

    public MyCalendarThree() {
        tree = new HashMap<Integer, Integer>();
        lazy = new HashMap<Integer, Integer>();
    }
    
    public int book(int startTime, int endTime) {
        update(startTime, endTime - 1, 0, 0, 1000000000);
        return tree.get(0);
    }
}

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

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-01-05 21:45:30
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-01-05 21:57:58
 */
package main

type pair_myCalendarIII struct {num, lazy int}
type MyCalendarThree map[int]pair_myCalendarIII

func max_MC3(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func Constructor() MyCalendarThree {
    return MyCalendarThree{}
}

func (this MyCalendarThree) update(start, end, index, l, r int) {
    if l > end || start > r {
        return
    }
    if l >= start && r <= end {
        p := this[index]
        p.num++  // 不可直接this[index].num++
        p.lazy++
        this[index] = p
    } else {
        mid := (l + r) >> 1
        this.update(start, end, index * 2 + 1, l, mid)
        this.update(start, end, index * 2 + 2, mid + 1, r)
        p := this[index]
        p.num = this[index].lazy + max_MC3(this[index * 2 + 1].num, this[index * 2 + 2].num)
        this[index] = p
    }
}

func (this MyCalendarThree) Book(startTime int, endTime int) int {
    this.update(startTime, endTime - 1, 0, 0, 1000000000)
    return this[0].num
}

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(startTime,endTime);
 */