56. Merge Intervals

Intitution

When intervals are unsorted, it’s hard to find overlaps. But if we sort all intervals by their start time, then we can easily compare each interval with the one before it to check for overlap.

If two intervals overlap, we can merge them by taking the earliest start and the latest end of the two. This way, we progressively build merged intervals while ensuring there are no overlaps in the final result.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(n + n\log(n))$

Code

public int[][] merge(int[][] intervals) {
    // Step 1: Sort intervals by their start time
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    // List to hold merged non-overlapping intervals
    List<int[]> mergedIntervals = new ArrayList<>();

    // Step 2: Start with the first interval as the previous one
    int[] previousInterval = intervals[0];

    // Step 3: Traverse remaining intervals
    for (int i = 1; i < intervals.length; ++i) {
        int[] currentInterval = intervals[i];

        // Step 4: If there's an overlap, merge current with previous
        if (currentInterval[0] <= previousInterval[1]) {
            // Extend the current interval to include the previous one
            currentInterval[0] = Math.min(currentInterval[0], previousInterval[0]);
            currentInterval[1] = Math.max(currentInterval[1], previousInterval[1]);
        } else {
            // No overlap: add the previous interval to the result
            mergedIntervals.add(previousInterval);
        }

        // Update previous to be the (possibly merged) current
        previousInterval = currentInterval;
    }

    // Step 5: Add the last interval
    mergedIntervals.add(previousInterval);

    // Step 6: Convert the result list to a 2D array
    int[][] result = new int[mergedIntervals.size()][2];
    for (int i = 0; i < mergedIntervals.size(); ++i) {
        result[i] = mergedIntervals.get(i);
    }

    return result;
}