[LeetCode] 729. My Calendar I

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:
MyCalendar() Initializes the calendar object.
boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:
Input
[“MyCalendar”, “book”, “book”, “book”]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints:
0 <= start < end <= 109
At most 1000 calls will be made to book.

我的日程安排表 I。

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

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

日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。

实现 MyCalendar 类：

MyCalendar() 初始化日历对象。
boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/my-calendar-i
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题目给的是一些日程安排，以 start 和 end 表示，应该是按数据流给出的，请你判断是否有安排冲突。

这道题我提供一个 treemap 的解法。这道题有点像扫描线那一类的题目，但是注意题目给的是数据流，数据不是一次性给出的。这里我们创建一个treemap<start, end>，存每一个安排的开始时间和结束时间。每当进来一个新的日程安排的时候（我们设这个日程安排为 A），我们用 A 的 start 去找 treemap 是否存在一个 floorKey，且这个 floorKey 的 end 是大于 A 的 start 的，如果有，就说明之前有一个安排的结束时间大于目前这个安排 A 的开始时间，冲突。

我们再用 A 的 start 去找 treemap 是否存在一个 ceilingKey，这个 ceilingKey 是另外一个安排 B 的开始时间，如果 B 存在且 B 的结束时间小于 A 的结束时间，也说明是冲突。

这两种冲突都不存在，我们才可以将 A 放入 treemap。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

class MyCalendar {
    TreeMap<Integer, Integer> map;

    public MyCalendar() {
        map = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Integer floorKey = map.floorKey(start);
        if (floorKey != null && map.get(floorKey) > start) {
            return false;
        }
        Integer ceilingKey = map.ceilingKey(start);
        if (ceilingKey != null && ceilingKey < end) {
            return false;
        }
        map.put(start, end);
        return true;
    }
}

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