Using 2 tree maps..


  • 0
    M
    class MyCalendarTwo {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    TreeMap<Integer, Integer> map2 = new TreeMap<>();
    
    public MyCalendarTwo() {    
    }
    
    public boolean book(int start, int end) {
        Map.Entry<Integer,Integer> lower = map2.lowerEntry(end);
        if(lower != null && lower.getValue() > start) return false;
        
        Map.Entry<Integer, Integer> higher = map2.higherEntry(start);
        if(higher != null && higher.getKey() < end) return false;
        
        lower = map.lowerEntry(start);
        if(lower != null && lower.getValue() > start) {
            map.remove(lower.getKey());
            map.put(start, lower.getValue());
            start = lower.getKey();
        }
        
        while(true) {
            higher = map.ceilingEntry(start);
            if(higher == null || higher.getKey() >= end) {
                map.put(start, end);
                break;
            } else {
                map.remove(higher.getKey());
                map.put(start, higher.getKey());
                start = Math.min(end, higher.getValue());
                end = Math.max(end, higher.getValue());
                map2.put(higher.getKey(), start);
                if(start == end) break;
            }
        }
        return true;
    }
    }

Log in to reply
 

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