My Calendar II


  • 0

    Click here to see the full article post


  • 0
    J

    I believe a Time: O(N ^ 2) Space: O(constant) is possible:

    Instead of storing all of the collisions in the Brute Force solution, check for this collision for every item against every other item, along with if the three events overlap. In the best case, this is worse than the brute force solution above time wise, but it should have the same worst case time and constant space

    for (event1 in calendar){
    if (event1 collides with newEvent) {
    for (event2 in calendar) {
    if (event2 != event (check by index) and event2 collides newEvent and event2 collides event1) {
    return false;
    }
    }
    }
    return true
    }


  • 0
    A

    In your second approach, there is no need to use ans variable.


  • 0
    S

    Why the time complexity of the second method is not O(N ^ N log(N)) ?


  • 0

    Why can't we use TreeMap or TreeSet for this problem? I'm not sure what's the problem with the following code... Can anybody tell me? Thanks.

    class MyCalendarTwo {
        TreeMap<Integer, Integer> map1; //store books
        TreeMap<Integer, Integer> map2; //store overlaps
        
        public MyCalendarTwo() {
            map1 = new TreeMap<>();
            map2 = new TreeMap<>();
        }
        
        public boolean book(int start, int end) {
            //check if overlaps with any overlap
            Integer pre2 = map2.floorKey(start);
            Integer next2 = map2.ceilingKey(start);
            
            if((pre2!=null && map2.get(pre2)>start) || (next2!=null && next2<end)) return false;
            
            //check if produce new overlaps
            Integer pre1 = map1.floorKey(start);
            Integer next1 = map1.ceilingKey(start);
            if(pre1!=null && map1.get(pre1)>start) map2.put(start, map1.get(pre1));
            if(next1!=null && next1<end) map2.put(next1, end);
            
            map1.put(start, end);
            return true;
        }
    }
    

  • 0
    A

    @ xxj79 The wrong thing is Treemap is only sorted by the key instead of by the value(end board). This is fine for the calendar 1. Because you always keep the elements in the map that the previous element's end board must bigger or equal to the next one's start. But for II, it is wrong. we you push intervals that overlapped into the map1.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.