Merge Intervals

Merge Intervals is a sorting and scanning problem. Given a list of intervals, the goal is to combine every overlapping range into one clean range.

The pattern is simple: sort intervals by start time, then keep comparing the current interval with the last interval already added to the result.

Problem

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return the non-overlapping result.

Example:

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

The intervals [1,3] and [2,6] overlap, so they become [1,6].

First Attempt

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;

    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    List<int[]> res = new ArrayList<>();

    for (int i = 0; i < intervals.length; i++) {
        if (res.isEmpty() || res.get(res.size() - 1)[1] < intervals[i][0]) {
            res.add(intervals[i]);
        } else {
            res.get(res.size() - 1)[1] = Math.max(
                    res.get(res.size() - 1)[1],
                    intervals[i][1]
            );
        }
    }

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

This is already the right idea.

The important move is sorting by the start of each interval before trying to merge anything.

Clean Version

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

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

        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();

        for (int[] current : intervals) {
            if (merged.isEmpty()) {
                merged.add(current);
                continue;
            }

            int[] last = merged.get(merged.size() - 1);

            if (last[1] < current[0]) {
                merged.add(current);
            } else {
                last[1] = Math.max(last[1], current[1]);
            }
        }

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

Why Sorting Works

After sorting, intervals appear in increasing start order:

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

Now the current interval only needs to be compared with the last merged interval.

If the current interval does not overlap, it can safely be added as a new range.

if (last[1] < current[0]) {
    merged.add(current);
}

If it overlaps, extend the end of the last merged interval.

last[1] = Math.max(last[1], current[1]);

Boundary Detail

The non-overlap condition is:

last[1] < current[0]

That means touching intervals are merged.

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

If the problem wanted touching intervals to stay separate, the condition would change to:

last[1] <= current[0]

For LeetCode Merge Intervals, touching intervals should be merged.

Walkthrough

Input:

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

Sorted input is the same:

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

current interval	last merged interval	action
`[1,3]`	none	add `[1,3]`
`[2,6]`	`[1,3]`	overlap, merge into `[1,6]`
`[8,10]`	`[1,6]`	no overlap, add `[8,10]`
`[15,18]`	`[8,10]`	no overlap, add `[15,18]`

Final result:

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

Complexity

Step	Time	Space
Sort intervals	`O(n log n)`	depends on sort implementation
Scan and merge	`O(n)`	`O(n)` for the result
Total	`O(n log n)`	`O(n)`

The scan is linear, but sorting dominates the runtime.

Takeaways

Sort intervals by start before merging.
Compare only with the last merged interval.
Use < for the non-overlap check when touching intervals should merge.
Update the end with Math.max(...) to keep the widest merged range.