Java Use of TreeMap


  • 0
    S
    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class SummaryRanges {
    
        TreeMap<Interval , Interval> map = null;
        public SummaryRanges() {
            map = new TreeMap<>(new Comparator<Interval>(){
                public int compare(Interval i1 , Interval i2) {
                    if(i1.start > i2.end) {
                        return 1;
                    } else if(i1.end < i2.start) {
                        return -1;
                    } else {
                        return 0;
                    }
                }    
            });
        }
        
        public void addNum(int val) {
            Interval interval = new Interval(val , val);
            
            if(map.containsKey(interval)) {
                return;
            } 
            
            Interval prev = new Interval(val -1,val-1);
            Interval next = new Interval(val + 1, val + 1);
            
            boolean mergePrev = map.containsKey(prev);
            boolean mergeNext = map.containsKey(next);
            
            if(mergePrev || mergeNext) {
                if(mergePrev && mergeNext) {
                    Interval toMerge1 = map.get(prev);
                    Interval toMerge2 = map.get(next);
                    map.remove(toMerge1); map.remove(toMerge2);
                    Interval newInterval = new Interval(toMerge1.start , toMerge2.end);
                    map.put(newInterval , newInterval);
                } else {
                    if(mergePrev) {
                        Interval toMerge = map.get(prev);
                        map.remove(toMerge);
                        Interval newInterval = new Interval(toMerge.start , val);
                        map.put(newInterval , newInterval);
                    } else {
                        Interval toMerge = map.get(next);
                        map.remove(toMerge);
                        Interval newInterval = new Interval(val , toMerge.end);
                        map.put(newInterval , newInterval);
                    }
                }
            } else {
                map.put(interval , interval);
            }
        }
        
        public List<Interval> getIntervals() {
            return new ArrayList<Interval>(map.keySet());
        }
    }
    
    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * List<Interval> param_2 = obj.getIntervals();
     */

Log in to reply
 

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