0731-我的日程安排表II

题目描述

https://leetcode.cn/problems/my-calendar-ii

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。

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

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例：

MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(50, 60); // returns true MyCalendar.book(10, 40); // returns true MyCalendar.book(5, 15); // returns false MyCalendar.book(5, 10); // returns true MyCalendar.book(25, 55); // returns true 解释：前两个日程安排可以添加至日历中。第三个日程安排会导致双重预订，但可以添加至日历中。第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。

提示：

每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。

思路

因为不能有重叠两次，所以最多重叠一次，当我们发现新加入的区间就在重叠区域时，就返回false。注意有两个地方

关于重叠区域，如果每次添加添加数据的时候才计算重叠区域，则要把原来的数据重新遍历一遍，时间复杂度很高，可以单独开辟一个数组储存重叠区域，这样新加入区间时只比较重叠区域就可以了
关于重叠区域的判断， [s1,e1) 和 [s2,e2) 如果 s1 < e2 且 s2 < e1 则会出现重叠，这个条件其实是 s1 >= e2 或者 s2 >=e1 的反条件。当一个区域的起点，在另一个区域终点后面的时候，他们必然是没有重叠的，反条件则是有重叠

csharp

public class MyCalendarTwo {

    private List<IList<int>> booked;
    private List<IList<int>> overlaps;

    public MyCalendarTwo() {
        booked = new List<IList<int>>();
        //把重叠的区域加进去，这样只需要判断是否在重叠区域里面
        overlaps = new List<IList<int>>();
    }
    
    public bool Book(int start, int end) {
        //对于区域 [s1,e1) 和 [s2,e2) 如果 s1 < e2 或者 s2 < e1 则会出现重叠
        for(int i=0; i<overlaps.Count; i++){
            int left = overlaps[i][0]; 
            int right = overlaps[i][1]; 
            if(start < right && left < end){
                return false;
            }
        }
        //加入区域，注意也加入重叠的区域 
        for(int i = 0; i<booked.Count; i++){
            int left = booked[i][0];
            int right = booked[i][1];
            //这里注意：求 left-->right 和 start-->end的交集
            //如果 left >= end 或者 start >= right 就没有交集了，所以条件如下
            if(left < end && start < right){
                overlaps.Add(new List<int>{ Math.Max(start,left), Math.Min(end,right) });
            }
        }
        booked.Add(new List<int>{start,end});
        return true;
    }
}

快速复习

csharp

public class MyCalendarTwo {

    private List<IList<int>> booked, overlaps;

    public MyCalendarTwo() {
        booked = new List<IList<int>>();
        overlaps = new List<IList<int>>();
    }
    
    public bool Book(int start, int end) {
        int start2 = start, end2 = end;
        for(int i=0; i<overlaps.Count; i++){
            int start1 = overlaps[i][0];
            int end1 = overlaps[i][1];
            if(start1 < end2 && start2 < end1){
                return false;
            }
        }
        for(int i=0; i<booked.Count; i++){
            int start1 = booked[i][0];
            int end1 = booked[i][1];
            if(start1 < end2 && start2 < end1){
                overlaps.Add(new List<int>{ Math.Max(start1,start2),Math.Min(end1,end2)  });
            }
        }
        booked.Add(new List<int>{start,end});
        return true;
    }
}

0731-我的日程安排表II #

题目描述 #

思路 #

快速复习 #

0731-我的日程安排表II

题目描述

思路

快速复习