L56 Merge Interval

Array

Problem

Given a collection of intervals, merge all overlapping intervals

Input: [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Problem analysis:

• For the intervals wee need to merger are overlapping, [1,3],[2,6] in these two, 3 and 2 should be deleted and got[1,6].

Solution:

• First, sort the interval by there starting points;

• Take the first interval, use its end index value to compare with the next interval's first index value.

  • if they overlap, update the end value to be the max end of the overlapping intervals.

  • Once find the non overlapping interval, add the previous "extended" interval and start over;

TC : sort takes n log(n), merge takes O(n), So, the resulting takes O(n log(n)).

SC: O(n)

• Used a lambda comparator (Java 8) and a for-each loop to try to keep the code clean and simple.

public int[][] merge(int[][] intervals){
    if(intervals.length <= 1) return intervals;
    
    Array.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[1]));
    
    List<int[]> res = new ArrayList<>();
    int[] newInterval = intervals[0];
    res.add(newInterval);
    for(int[] interval : intervals){
        if(interval[0] <= intervals[1]{
            newInterval[1] = Math.max(newInterval[1], interval[1]);
        }else{
            newInterval = interval;
            res.add(newInterval);
        }
    }
    return result.toArray(new int[result.size()][]);
}