Java with binary search tree solution


  • 0
    B
    public class SummaryRanges {
        TreeMap<Integer, Interval> starts = new TreeMap<>();
        /** Initialize your data structure here. */
        public SummaryRanges() {
            
        }
        
        private void addInterval(Interval interval) {
            if(starts.containsKey(interval.end+1)) { 
                Interval newInterval = new Interval(interval.start, starts.get(interval.end+1).end);
                starts.remove(interval.end+1);
                addInterval(newInterval);
            } else {
                Map.Entry<Integer, Interval> previous = starts.lowerEntry(interval.start);
                if(null!=previous && previous.getValue().end+1==interval.start) {
                    Interval newInterval = new Interval(previous.getValue().start, interval.end);
                    starts.remove(previous.getKey());
                    addInterval(newInterval);
                } else {
                    starts.put(interval.start, interval);
                }
            }
        }
        
        public void addNum(int val) {
            if(starts.containsKey(val)) return;
            Map.Entry<Integer, Interval> previous = starts.lowerEntry(val);
            if(null!=previous && val <= previous.getValue().end) return;
            else {
                Map.Entry<Integer, Interval> next = starts.higherEntry(val);
                if(null==next && starts.size()>0 && starts.lastEntry().getValue().end>=val) return;
            }
            addInterval(new Interval(val, val));
        }
        
        public List<Interval> getIntervals() {
            List<Interval> list = new LinkedList<>();
            list.addAll(starts.values());
            return list;
        }
    }

Log in to reply
 

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