Merge Intervals

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.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Example 3:

Input: intervals = [[4,7],[1,4]] Output: [[1,7]] Explanation: Intervals [1,4] and [4,7] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Approach: Sort and Merge

Algorithm

1. Sort the intervals by their start value
2. Initialize the merged list with the first interval
3. For each subsequent interval, if it overlaps with the last merged interval, extend the end
4. Otherwise, add it as a new interval
5. Return the merged list

Time & Space Complexity

• Time Complexity: O(n log n) - dominated by sorting
• Space Complexity: O(n) - the merged list (and sorting space)

Java Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeIntervals {

    /**
     * Merge all overlapping intervals.
     * @param intervals Array of [start, end] intervals
     * @return Merged non-overlapping intervals
     */
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        merged.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            int[] last = merged.get(merged.size() - 1);
            int[] current = intervals[i];

            if (current[0] <= last[1]) {
                // Overlap: extend the end
                last[1] = Math.max(last[1], current[1]);
            } else {
                merged.add(current);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }

    // Test method
    public static void main(String[] args) {
        int[][] intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        System.out.println("Input: intervals = [[1,3],[2,6],[8,10],[15,18]]");
        System.out.println("Output: " + Arrays.deepToString(merge(intervals1)));
        // Expected: [[1,6],[8,10],[15,18]]

        int[][] intervals2 = {{1, 4}, {4, 5}};
        System.out.println("Input: intervals = [[1,4],[4,5]]");
        System.out.println("Output: " + Arrays.deepToString(merge(intervals2)));
        // Expected: [[1,5]]

        int[][] intervals3 = {{4, 7}, {1, 4}};
        System.out.println("Input: intervals = [[4,7],[1,4]]");
        System.out.println("Output: " + Arrays.deepToString(merge(intervals3)));
        // Expected: [[1,7]]
    }
}

Example Walkthrough

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

1. Sort by start: already sorted
2. Start merged = [[1,3]]
3. [2,6]: 2 <= 3, overlap, merge -> [1,6]
4. [8,10]: 8 > 6, new interval -> [[1,6],[8,10]]
5. [15,18]: 15 > 10, new interval -> [[1,6],[8,10],[15,18]]

Key Points

1. Sort First: Sorting by start makes merging a single linear pass
2. Overlap Condition: Intervals [a, b] and [c, d] overlap if c <= b
3. Touching Counts: [1,4] and [4,5] merge because 4 <= 4
4. In-Place End Update: Extending last[1] mutates the stored interval
5. O(n log n): Sorting dominates; merging itself is O(n)