Merge Intervals

intervalssorting

Problem

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.

Examples

Example 1

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

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

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

Example 2

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

Output: [[1,5]]

Explanation: Touching intervals (end == next start) count as overlapping.

Constraints

•1 <= intervals.length <= 10^4
•intervals[i].length == 2
•0 <= starti <= endi <= 10^4

Hints

Hint 1

The brute force repeatedly scans for any overlapping pair and merges it, looping until no overlaps remain — correct, but potentially many passes over the data.

Hint 2

If the intervals were processed in START-TIME order, could a merge decision ever need to look further back than the single most recently merged interval?

Hint 3

Sort by start time first (O(n log n), a one-time cost) — this reduces the whole problem to a single linear sweep, comparing each interval only against the last one merged so far.

Solutions

public int[][] mergeBruteForce(int[][] intervals) {
    List<int[]> result = new ArrayList<>(Arrays.asList(intervals));
    boolean mergedAny = true;
    while (mergedAny) {
        mergedAny = false;
        outer:
        for (int i = 0; i < result.size(); i++) {
            for (int j = i + 1; j < result.size(); j++) {
                int[] a = result.get(i), b = result.get(j);
                if (a[0] <= b[1] && b[0] <= a[1]) { // overlap check
                    result.set(i, new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])});
                    result.remove(j);
                    mergedAny = true;
                    break outer;
                }
            }
        }
    }
    return result.toArray(new int[result.size()][]);
}

Time: O(n^3) worst case (repeated O(n^2) scans) · Space: O(n)