shared my very short and fast java solution(174ms)


  • 0
    L

    using hashmap & treemap & hashset

    /**
     * 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 {
    
        /** Initialize your data structure here. */
        Set<Integer> pointSet = new HashSet<Integer>();
        
    //    Map<Integer, Interval>
            
        Map<Integer, Interval> st2intervalMap = new TreeMap<Integer, Interval>();
        Map<Integer, Interval> ed2intervalMap = new HashMap<Integer, Interval>();
        //Set<Interval> intervalSet = new TreeSet<Interval>(new IntervalComparator());
        
        public SummaryRanges() {
            
        }
        
        public void addNum(int val) {
            if (pointSet.contains(val)) return;
            int mergedL = val,mergedR = val;
            if (pointSet.contains(val - 1)) {
                Interval lInterval = ed2intervalMap.get(val - 1);
                mergedL = Math.min(lInterval.start, mergedL);
                st2intervalMap.remove(lInterval.start);
                ed2intervalMap.remove(lInterval.end);
            }
            if (pointSet.contains(val + 1)) {
                Interval rInterval = st2intervalMap.get(val + 1);
                mergedR = Math.max(rInterval.end, mergedR);
                st2intervalMap.remove(rInterval.start);
                ed2intervalMap.remove(rInterval.end);
            }
            Interval mergedInterval =  new Interval(mergedL, mergedR);
            st2intervalMap.put(mergedL, mergedInterval);
            ed2intervalMap.put(mergedR, mergedInterval);
            
      
            
            pointSet.add(val);
            
            
        }
        
        public List<Interval> getIntervals() {
            return new ArrayList<Interval>(st2intervalMap.values());
        }
    }
    
    /**
     * 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.