Merge Intervals

Problem Statement

LeetCode-56: Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

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

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

Approach

The problem can be solved by sorting the intervals based on the start time and then merging the intervals. We can iterate over the sorted intervals and merge the intervals if they overlap.

1. Sort the intervals based on the start time.
2. Initialize a list to store the merged intervals.
3. Initialize prev interval as the first interval in the sorted list.
4. Iterate over the sorted intervals from second interval. Let’s call each interval as next.
   1. If the next interval overlaps with the prev interval in the merged list, merge the intervals.
   2. Else, add the prev interval to the merged list.
5. Return the merged list.

Implementation

Here is a Java implementation of the above approach:

public int[][] merge(int[][] intervals) {
    // sort input on start time
    Arrays.sort(intervals, (prev, next) -> Integer.compare(prev[0], next[0]));
    
    List<int[]> merged = new ArrayList<>();
    int[] prev = intervals[0];

    for (int i = 1; i < intervals.length; i++) {
        int[] next = intervals[i];
        // if overlap, merge the intervals
        if (prev[1] >= next[0]) {
            prev = new int[]{Math.min(prev[0], next[0]), Math.max(prev[1], next[1])};
        } 
        // else add the prev interval to the merged list
        // and update prev to next
        else {
            merged.add(prev);
            prev = next;
        }
    }

    merged.add(prev);
    return merged.toArray(new int[0][0]);
}

Complexity Analysis

The time complexity for this approach is $O(N \log N)$, where $N$ is the number of intervals. The complexity arises from sorting the intervals based on the start time. The space complexity is $O(N)$, due to the space required to store the merged intervals.