Simple Java solution without sort (372 ms)


  • 0
    A
    /**
     * 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 Solution {
        public List<Interval> merge(List<Interval> intervals) {
            List<Interval> result = new ArrayList<Interval>();
            
            if (intervals != null) {
                for (int i=0;i<intervals.size();i++){
                    Interval next = intervals.get(i);
                    int j=0;
                    while (j<result.size()){
                        Interval added = result.get(j);
    
                        // Not overlapping
                        if (next.start > added.end || next.end < added.start) {
                            j++;
                            continue;
                        } else { // In case of overlapping new Interval will include previously added
                            if (added.start < next.start)
                                next.start = added.start;
                            if (added.end > next.end)
                                next.end = added.end;
                            result.remove(j); // Remove previously added interval
                        }
                    }
                    
                    result.add(next);
                }
            }
            
            return result;
        }
    }

Log in to reply
 

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