列表

详情

732. 我的日程安排表 III

当 k 个日程安排有一些时间上的交叉时（例如 k 个日程安排都在同一时间内），就会产生 k 次预订。

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

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

 

示例：

输入：
["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

 

提示：

相似题目

我的日程安排表 I

我的日程安排表 II

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class MyCalendarThree { public: MyCalendarThree() { } int book(int start, int end) { } }; /** * Your MyCalendarThree object will be instantiated and called as such: * MyCalendarThree* obj = new MyCalendarThree(); * int param_1 = obj->book(start,end); */

javascript 解法, 执行用时: 107 ms, 内存消耗: 69.4 MB, 提交时间: 2025-01-04 08:32:23 

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

MyCalendarThree.prototype.book = function(start, end) {
    this.update(start, end - 1, 0, 1000000000, 1);
    return this.tree.get(1) || 0;
};

MyCalendarThree.prototype.update = function(start, end, l, r, idx) {
    if (r < start || end < l) {
        return;
    } 
    if (start <= l && r <= end) {
        this.tree.set(idx, (this.tree.get(idx) || 0) + 1);
        this.lazy.set(idx, (this.lazy.get(idx) || 0) + 1);
    } else {
        const mid = (l + r) >> 1;
        this.update(start, end, l, mid, 2 * idx);
        this.update(start, end, mid + 1, r, 2 * idx + 1);
        this.tree.set(idx, (this.lazy.get(idx) || 0) + Math.max((this.tree.get(2 * idx) || 0), (this.tree.get(2 * idx + 1) || 0)));
    }
}

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * var obj = new MyCalendarThree()
 * var param_1 = obj.book(start,end)
 */

cpp 解法, 执行用时: 37 ms, 内存消耗: 32.2 MB, 提交时间: 2025-01-04 08:32:05 

class MyCalendarThree {
public:
    MyCalendarThree() {
        
    }
    
    int book(int start, int end) {
        int ans = 0;
        int maxBook = 0;
        cnt[start]++;
        cnt[end]--;
        for (auto &[_, freq] : cnt) {
            maxBook += freq;
            ans = max(maxBook, ans);
        }
        return ans;
    }
private:
    map<int, int> cnt;
};

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

cpp 解法, 执行用时: 341 ms, 内存消耗: 201.6 MB, 提交时间: 2025-01-04 08:31:50 

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;
    }
};

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

java 解法, 执行用时: 118 ms, 内存消耗: 49.8 MB, 提交时间: 2025-01-04 08:31:23 

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

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

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

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

java 解法, 执行用时: 113 ms, 内存消耗: 44.6 MB, 提交时间: 2025-01-04 08:31:07 

class MyCalendarThree {
    private TreeMap<Integer, Integer> cnt;

    public MyCalendarThree() {
        cnt = new TreeMap<Integer, Integer>();
    }
    
    public int book(int start, int end) {
        int ans = 0;
        int maxBook = 0;
        cnt.put(start, cnt.getOrDefault(start, 0) + 1);
        cnt.put(end, cnt.getOrDefault(end, 0) - 1);
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int freq = entry.getValue();
            maxBook += freq;
            ans = Math.max(maxBook, ans);
        }
        return ans;
    }
}

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

golang 解法, 执行用时: 128 ms, 内存消耗: 8.9 MB, 提交时间: 2022-11-21 10:17:05 

type pair struct{ num, lazy int }

type MyCalendarThree map[int]pair

func Constructor() MyCalendarThree {
    return MyCalendarThree{}
}

func (t MyCalendarThree) update(start, end, l, r, idx int) {
    if r < start || end < l {
        return
    }
    if start <= l && r <= end {
        p := t[idx]
        p.num++
        p.lazy++
        t[idx] = p
    } else {
        mid := (l + r) / 2
        t.update(start, end, l, mid, idx*2)
        t.update(start, end, mid+1, r, idx*2+1)
        p := t[idx]
        p.num = p.lazy + max(t[idx*2].num, t[idx*2+1].num)
        t[idx] = p
    }
}

func (t MyCalendarThree) Book(start, end int) int {
    t.update(start, end-1, 0, 1e9, 1)
    return t[1].num
}

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


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

golang 解法, 执行用时: 112 ms, 内存消耗: 7 MB, 提交时间: 2022-11-21 10:16:48 

type MyCalendarThree struct {
    *redblacktree.Tree
}

func Constructor() MyCalendarThree {
    return MyCalendarThree{redblacktree.NewWithIntComparator()}
}

func (t MyCalendarThree) add(x, delta int) {
    if val, ok := t.Get(x); ok {
        delta += val.(int)
    }
    t.Put(x, delta)
}

func (t MyCalendarThree) Book(start, end int) (ans int) {
    t.add(start, 1)
    t.add(end, -1)

    maxBook := 0
    for it := t.Iterator(); it.Next(); {
        maxBook += it.Value().(int)
        if maxBook > ans {
            ans = maxBook
        }
    }
    return
}


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

python3 解法, 执行用时: 888 ms, 内存消耗: 20.6 MB, 提交时间: 2022-11-21 10:16:33 

'''
线段树
'''
class MyCalendarThree:
    def __init__(self):
        self.tree = defaultdict(int)
        self.lazy = defaultdict(int)

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

    def book(self, start: int, end: int) -> int:
        self.update(start, end - 1, 0, 10 ** 9, 1)
        return self.tree[1]

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

python3 解法, 执行用时: 1504 ms, 内存消耗: 15.9 MB, 提交时间: 2022-11-21 10:16:14 

'''
差分数组
'''
from sortedcontainers import SortedDict

class MyCalendarThree:
    def __init__(self):
        self.d = SortedDict()

    def book(self, start: int, end: int) -> int:
        self.d[start] = self.d.setdefault(start, 0) + 1
        self.d[end] = self.d.setdefault(end, 0) - 1

        ans = maxBook = 0
        for freq in self.d.values():
            maxBook += freq
            ans = max(ans, maxBook)
        return ans

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

上一题

© 2025 leetcode.cn