LeetCode Problem 56 Merge Intervals

1. Problem Summary

You are given an array of intervals, where each interval is represented as:

[ start, end ]

Your task is to:

Merge all overlapping intervals
Return a new list of intervals that are non-overlapping and cover all the intervals in the input.

Important details:

Intervals may be unsorted.
Intervals may overlap partially or fully.
The resulting intervals must be sorted by start time and non-overlapping.

Example:
Input:

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

Output:

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

Because [1,3] and [2,6] overlap and merge into [1,6].

2. Key Insights

1. Sorting by start time is crucial

If intervals are sorted by their start value:

We can sweep from left to right.
Any overlap will occur only between the current interval and the last interval in our result list.

2. When do intervals overlap?

Two intervals [aStart, aEnd] and [bStart, bEnd] overlap if:

bStart <= aEnd

(assuming aStart <= bStart because of sorting)

3. How to merge overlapping intervals?

If there is an overlap:

mergedEnd = max(aEnd, bEnd)

So [aStart, aEnd] and [bStart, bEnd] merge to:

[aStart, max(aEnd, bEnd)]

4. Non-overlapping intervals are just appended

If the current interval starts after the last merged interval ends:

current.start > last.end

Then they do not overlap, and we just add the current interval as a new one.

3. Approach

Step-by-step strategy

If the input array is empty, return an empty array.
Sort the intervals by their start value.
Initialize a result list and push the first interval into it.
For each subsequent interval:
- Compare it with the last interval in the result list.
- If they overlap, merge them by updating the end of the last interval.
- If they do not overlap, append the current interval to the result list.
Convert the result list back to a 2D array and return it.

This is a classic sweep-line style algorithm on intervals.

4. Time and Space Complexity

Time Complexity

Sorting: O(N log N)
Single pass to merge: O(N)
Overall:

O(N log N)

Space Complexity

Result list holds at most N intervals.
Sorting may be in-place (depending on implementation).

Auxiliary (extra) space is:

O(N)  // for the output

5. Java Solution

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][];
        }

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

        List<int[]> merged = new ArrayList<>();
        // Start with the first interval
        int[] current = intervals[0];
        merged.add(current);

        // Step 2: Iterate and merge
        for (int i = 1; i < intervals.length; i++) {
            int[] next = intervals[i];

            int currentStart = current[0];
            int currentEnd = current[1];
            int nextStart = next[0];
            int nextEnd = next[1];

            if (nextStart <= currentEnd) {
                // Overlap: merge intervals
                current[1] = Math.max(currentEnd, nextEnd);
            } else {
                // No overlap: move to next interval
                current = next;
                merged.add(current);
            }
        }

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

6. Dry Run Examples

Example 1

Input:

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

Step 1: Sort by start:

[[1,3],[2,6],[8,10],[15,18]]  // already sorted

Initialize:

merged = [[1,3]]
current = [1,3]

Process [2,6]:

Compare with current = [1,3]
nextStart = 2, currentEnd = 3
2 <= 3 → overlap
Merge: current = [1, max(3,6)] = [1,6]
merged = [[1,6]]

Process [8,10]:

current = [1,6]
nextStart = 8, currentEnd = 6
8 > 6 → no overlap
Add new interval:
- merged = [[1,6],[8,10]]
- current = [8,10]

Process [15,18]:

current = [8,10]
nextStart = 15, currentEnd = 10
15 > 10 → no overlap
merged = [[1,6],[8,10],[15,18]]

Final output:

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

Example 2

Input:

[[1,4],[4,5]]

Sorted:

[[1,4],[4,5]]

Initialize:

merged = [[1,4]]
current = [1,4]

Process [4,5]:

nextStart = 4, currentEnd = 4
4 <= 4 → overlap (touching endpoints is still considered overlapping)
Merge:
- current = [1, max(4,5)] = [1,5]
- merged = [[1,5]]

Output:

[[1,5]]

Example 3

Input:

[[1,2],[3,4],[5,6]]

All intervals are disjoint.

Sorted (already):

[[1,2],[3,4],[5,6]]

Walk-through:

Start: merged = [[1,2]]
[3,4] → no overlap with [1,2] → merged = [[1,2],[3,4]]
[5,6] → no overlap with [3,4] → merged = [[1,2],[3,4],[5,6]]

Output:

[[1,2],[3,4],[5,6]]

Example 4 (unsorted input)

Input:

[[6,8],[1,9],[2,4],[4,7]]

Sorted by start:

[[1,9],[2,4],[4,7],[6,8]]

Now merge:

Start: merged = [[1,9]] (current = [1,9])

Check [2,4]:
2 <= 9 → merge into [1,9]

Check [4,7]:
4 <= 9 → merge into [1,9]

Check [6,8]:
6 <= 9 → merge into [1,9]

All merged to a single interval:

Output:

[[1,9]]

7. Why This Solution Works

Sorting ensures that when we see an interval, all possible overlaps must be with the last merged interval only.
This allows a single scan with a simple condition to decide:
- merge (update end)
- or append a new interval.
No need for nested loops or checking all pairs once sorted.
Time complexity is optimal for any solution that must consider all intervals.

8. Common Mistakes

Forgetting to sort intervals before merging.
Treating intervals that touch at endpoints (like [1,4] and [4,5]) as non-overlapping when the problem considers them overlapping.
Modifying the merged list incorrectly (e.g., not updating the last interval in-place).
Using an overly complex data structure when a simple list is enough.
Off-by-one mistakes in boundary checks.