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