729. My Calendar I

二刷 08/2022

Version #1 TreeMap

一个bug，如果用floorKey(end)的话//  [19,25)[25,32)[33,41)[47,50) 要加入[19,25)就会失败，因为25的floorKey是[25,32)entry，然后32又比19大

所以应该用lowerKey

注意这里没有必要合并相邻的intervals

Time O(logN)

Space O(N)

Runtime: 30 ms, faster than 75.04% of Java online submissions for My Calendar I.

Memory Usage: 54.6 MB, less than 51.82% of Java online submissions for My Calendar I.

class MyCalendar {

    TreeMap<Integer, Integer> events;

    public MyCalendar() {

        this.events = new TreeMap<>();

    }

    

    //  [19,25)[25,32)[33,41)[47,50)

    

    public boolean book(int start, int end) {

        // [start, end)

        Integer prevStart = events.lowerKey(end);

        if (prevStart != null && events.get(prevStart) > start) {

            return false;

        }

        // [prevStart, prevEnd) [start, end)

        events.put(start, end);

        return true;

    }

}

一刷
Version #1 TreeMap

Time O(logn) for each book() call

94.57 %
class MyCalendar {

    TreeMap<Integer, Integer> treeMap;
public MyCalendar() {
// key-start, value-end
this.treeMap = new TreeMap<>();
}

public boolean book(int start, int end) {
// [start, end)    [start, end)
// There should be two constraints
// 1.any event happens after current start time, should start after end time
// 2.any event happens before current start time, should end before start time
Map.Entry<Integer, Integer> prev = treeMap.floorEntry(start);
if (prev != null && prev.getValue() > start) return false;
Map.Entry<Integer, Integer> next = treeMap.ceilingEntry(start);
if (next != null && next.getKey() < end) return false;
treeMap.put(start, end);
return true;
}
}