731. 我的日程安排表 II

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

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

事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为  startTime <= x < endTime。

实现 MyCalendarTwo 类：

• MyCalendarTwo() 初始化日历对象。

• boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

思路

既然不能产生三重预订，那就是二重预订是允许的，所以记录一个二重预订的队列和一个一重预定的队列。每次调用book 函数的时候，先去二重预订的队列进行比对，如果有重叠，说明产生了三重预订，返回false。否则，与一重预定进行比对，如果发生重复，增添一个二重预定的数组到二重预定队列中。

技巧

当判断两个数组之间是否有重叠时，如[start1, end1]与[start2, end2] 。

即可写为 start1 < end2 && start2 < end1 即可！

代码

class MyCalendarTwo {
    Queue<int[]> queue;
    Queue<int[]> doubleQueue;
    public MyCalendarTwo() {
        queue = new PriorityQueue<>((o1, o2)->o1[0]-o2[0]);
        doubleQueue = new PriorityQueue<>((o1, o2)->o1[0]-o2[0]);
    }
    
    public boolean book(int startTime, int endTime) {
        for (int[] time : doubleQueue) {
            if (startTime < time[1] && time[0] < endTime) 
                return false;
        }
        for (int[] time : queue) {
            if (startTime < time[1] && time[0] < endTime) 
                doubleQueue.offer(new int[]{Math.max(startTime, time[0]), Math.min(endTime, time[1])});
        }
        queue.offer(new int[]{startTime, endTime});
        return true;
    }
}