729. My Calendar I

开源项目 leetcode刷题区
1

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end) . Formally, this represents a booking on the half open interval [start, end) , the range of real numbers x such that start <= x < end .

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book , return 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.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example 1:

MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(15, 25); // returns false MyCalendar.book(20, 30); // returns true Explanation: The first event can be booked. The second can’t because time 15 is already booked by another event. The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

  • The number of calls to MyCalendar.book per test case will be at most 1000 .
  • In calls to MyCalendar.book(start, end) , start and end are integers in the range [0, 10^9] .

java

使用TreeMap，因为它可以得到floorKey和ceilingKey，前者得到刚好小于等于srart的key1，后者得到刚好大于等于start的key2。

步骤1：从treemap中找到刚好小于等于srart的key1

  • 如果key1为null，说明键都比start大，继续判断
  • 如果key1为非null，说明存在一个键刚好小于start，那么判断这个键的值是否大于start，如果大于start，说明之前存储过一个(start1， end2)，它与现在的(start，end)有交集，返回false，否则继续判断

步骤2：从treemap中找到刚好大于等于srart的key2

  • 如果key2为null，说明treemap中的key（存储过的start）都小于新的start，并且也满足条件1，继续操作
  • 如果key2存在，且其值小于新end，说明存在交集，返回false

步骤3：新值存入treemep，返回true

时间复杂度与空间复杂度

image
image841×260 15 KB 

class MyCalendar {
   
    TreeMap<Integer, Integer> calendar;

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

    public boolean book(int start, int end) {
        //返回最大键小于等于给定键；如果不存在则返回null
        Integer floorKey = calendar.floorKey(start);
        if (floorKey != null && calendar.get(floorKey) > start) return false;
        //返回最小键大于或等于给定的值，如果不存在则返回null
        Integer ceilingKey = calendar.ceilingKey(start);
        if (ceilingKey != null && ceilingKey < end) return false;

        calendar.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);
 */