Merge Intervals

Problem Description

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

Examples

Constraints

• 1 ≤ intervals.length ≤ 10⁴
• intervals[i].length == 2
• 0 ≤ start ≤ end ≤ 10⁴

Consolidating Overlapping Boundaries in Sorted Order

If the intervals are unsorted, we must compare every interval against every other interval, which takes O(n²) time.

By sorting the intervals by their start coordinates first, we ensure that overlapping intervals are adjacent in the list.

• We start by adding the first interval to our result list.
• For each subsequent interval, we compare its start value against the end value of the last interval in our result list.
• If they overlap (meaning current_start <= last_inserted_end), we merge them by updating the end value of the last inserted interval: last_inserted_end = max(last_inserted_end, current_end).
• If they do not overlap, we append the current interval to our result list as a new entry.

Solution 1: Sort and Merge (Optimal)

Sort the input by start coordinate, then iterate and merge overlaps in-place or into a new list.

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;

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

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

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

            if (curr[0] <= last[1]) {
                // overlap: merge by extending the end boundary
                last[1] = Math.max(last[1], curr[1]);
            } else {
                // no overlap: append new interval
                result.add(curr);
            }
        }

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

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        if len(intervals) <= 1:
            return intervals

        # sort by start coordinate
        intervals.sort(key=lambda x: x[0])

        result = [intervals[0]]

        for i in range(1, len(intervals)):
            last = result[-1]
            curr = intervals[i]

            if curr[0] <= last[1]:
                # overlap: merge by extending the end boundary
                last[1] = max(last[1], curr[1])
            else:
                # no overlap: append new interval
                result.append(curr)

        return result

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
        if (intervals.size() <= 1) return intervals;

        // sort by start coordinate
        std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });

        std::vector<std::vector<int>> result;
        result.push_back(intervals[0]);

        for (size_t i = 1; i < intervals.size(); i++) {
            auto& last = result.back();
            auto& curr = intervals[i];

            if (curr[0] <= last[1]) {
                // overlap: merge by extending the end boundary
                last[1] = std::max(last[1], curr[1]);
            } else {
                // no overlap: append new interval
                result.push_back(curr);
            }
        }

        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n) where n is the number of intervals. Sorting dominates the execution time. The merge pass is a linear O(n) scan.
• Space Complexity: O(n) or O(log n) depending on the sorting algorithm implementation (e.g. quicksort recursion stack).

Where it breaks: Nothing breaks for standard ranges. If interval values can exceed standard integer bounds (which is not possible with these constraints), the subtraction in custom Java comparator lambdas (a, b) -> a[0] - b[0] can overflow. Using Integer.compare prevents this.

Common Mistakes

• Not sorting the intervals array first. If the input is not sorted, adjacent checks will miss overlaps between non-adjacent elements (e.g., [[1, 4], [5, 6], [2, 3]]).
• Using simple subtraction for sorting comparators in Java. Writing (a, b) -> a[0] - b[0] can result in integer overflow if coordinates contain extreme negative and positive values. Use Integer.compare to be safe.
• Replacing instead of extending the end boundary during merge. If merging [1, 4] and [2, 3], the result must be [1, 4]. If you simply overwrite the end value with the current end value, you get [1, 3], which is incorrect. Use max(last[1], curr[1]).

Frequently Asked Questions

Are touching boundaries (like [1, 4] and [4, 5]) considered overlapping? Yes. The problem constraints define touch-point boundaries as overlapping. We check curr[0] <= last[1], which evaluates to true when 4 <= 4.

Can we merge intervals in O(n) time without sorting? Only if the coordinates are constrained to a small range, allowing bucket sort or counting sort. For general coordinates, sorting is mandatory, making the lower bound O(n log n).

What does this problem test in interviews? It tests your understanding of coordinate boundaries, custom sorting comparators, and linear list reduction techniques.

← All Problems