Clean O(n*log(n)) time, O(n) space solution in Java


  • 0
    T

    This solutions relies on an initial sort and then scans the sorted list once, while assembling the result final list.

    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            
            if (intervals.size() == 0) return intervals;
            
            // sort intervals by first element
            Collections.sort(intervals, new Comparator<Object>(){
                public int compare(Object o1, Object o2) {
                    
                    Interval i1 = (Interval) o1;
                    Interval i2 = (Interval) o2;
                    
                    
                    if      (i1.start == i2.start) return 0;
                    else if (i1.start < i2.start)  return -1;
                    else                           return 1;
                    
                }
            });
            
            List<Interval> result = new LinkedList<>();
            
            // set a current start and current end
            int curStart = intervals.get(0).start;
            int curEnd = intervals.get(0).end;
            
            // go through interval, if first start falls within current overlap, update end
            for (Interval i : intervals) {
                
                // check if this interval is not outside current
                if (i.start <= curEnd) {
                    // extend current interval if this interval is not purely inside
                    curEnd = Math.max(curEnd, i.end);     
                }
                else {
                    
                    result.add(new Interval(curStart, curEnd));
                    curStart = i.start;
                    curEnd = i.end;
                }
            }
            
            result.add(new Interval(curStart, curEnd));
            
            return result;
            
        }
    }
    

Log in to reply
 

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