Nlogn solution using TreeMap


  • 0
    S
    public class SummaryRanges {
    
        /** Initialize your data structure here. */
        TreeMap<Integer, Interval> map;
        public SummaryRanges() {
            map = new TreeMap<>();
        }
        
        public void addNum(int val) {
                Interval interval = new Interval(val, val);
            Integer floor = map.floorKey(val);
            Integer ceiling = map.ceilingKey(val);
            
            if(floor == null && ceiling != null) {
                if(val >= map.get(ceiling).start && val <= map.get(ceiling).end) {
                    return;
                } else if(map.get(ceiling).start == val+1) {
                    map.put(val, new Interval(val, map.get(ceiling).end));
                    map.remove(ceiling);
                    return;
                } 
            }
            
            if(floor != null && ceiling == null) {
                if(val >= map.get(floor).start && val <= map.get(floor).end) {
                    return;
                } else if(map.get(floor).end == val-1) {
                    map.put(map.get(floor).start, new Interval(map.get(floor).start, val));
                    return;
                }
            }
            if(floor != null && ceiling != null) {
                if((val >= map.get(floor).start && val <= map.get(floor).end) || (val >= map.get(ceiling).start && val <= map.get(ceiling).end)) {
                    return;
                }
                if(map.get(floor).end == val-1 && map.get(ceiling).start == val+1) {
                    map.put(map.get(floor).start, new Interval(map.get(floor).start, map.get(ceiling).end));
                    map.remove(ceiling);
                    return;
                } else if(map.get(floor).end == val-1) {
                    map.put(map.get(floor).start, new Interval(map.get(floor).start, val));
                    return;
                } else if(map.get(ceiling).start == val+1) {
                    map.put(val, new Interval(val, map.get(ceiling).end));
                    map.remove(ceiling);
                    return;
                }
            } 
            
            map.put(val, interval);
        }
        
        public List<Interval> getIntervals() {
            List<Interval> result = new ArrayList<>();
            for(Map.Entry<Integer, Interval> entry: map.entrySet()) {
                result.add(entry.getValue());
            }
            return result;
        }
    }

Log in to reply
 

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