731.我的日程安排表II

链接：731.我的日程安排表II
难度：Medium
标签：设计、线段树、数组、二分查找、有序集合、前缀和
简介：实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

题解 1 - rust

• 编辑时间：2022-07-19
• 执行用时：28ms
• 内存消耗：2.7MB
• 编程语言：rust
• 解法介绍：记录已经重叠的部分，每次遍历时判断新添加的是否和已重叠部分有冲突。

struct MyCalendarTwo {
    list: Vec<(i32, i32)>,
    overlap: Vec<(i32, i32)>,
}
impl MyCalendarTwo {
    fn new() -> Self {
        MyCalendarTwo {
            list: Vec::new(),
            overlap: Vec::new(),
        }
    }
    fn book(&mut self, start: i32, end: i32) -> bool {
        let block = (start, end);
        for item in &self.overlap {
            if self.is_overlap(&block, item) {
                return false;
            }
        }
        for item in &self.list {
            if self.is_overlap(&block, item) {
                self.overlap.push((block.0.max(item.0), block.1.min(item.1)));
            }
        }
        self.list.push(block);
        print!("{}", block.0);
        true
    }
    fn is_overlap(&self, v1: &(i32, i32), v2: &(i32, i32)) -> bool {
        v1.0 < v2.1 && v1.1 > v2.0
    }
}

题解 2 - python

• 编辑时间：2025-01-03
• 执行用时：2079ms
• 内存消耗：18.68MB
• 编程语言：python
• 解法介绍：差分记录区间内已经订阅的课程数量

def has_intersection(a1: int, b1: int, a2: int, b2: int) -> int:
    return a1 < b2 and a2 < b1
class MyCalendarTwo:
    def __init__(self):
        self.map = SortedDict()
    def book(self, startTime: int, endTime: int) -> bool:
        cnt = 0
        for v1, v2 in pairwise(self.map.items()):
            cnt += v1[1]
            if has_intersection(startTime, endTime, v1[0], v2[0]) and cnt == 2:
                return False
        self.map.setdefault(startTime, 0)
        self.map.setdefault(endTime, 0)
        self.map[startTime] += 1
        self.map[endTime] -= 1
        if self.map[endTime] == 0: self.map.pop(endTime)
        return True