Skip to main content
CodePeetCodePeet
CodePeet 250

Merge Intervals

MEDIUMProblemSolveExternal Links

Description

You are given a collection of intervals, where each interval is represented as a pair of integers [start, end]. Your task is to merge all intervals that overlap with each other, and return a new collection of non-overlapping intervals that together cover every range present in the original input.

Two intervals overlap if one starts before or at the point where the other ends. For example, [1, 3] and [2, 6] overlap because the second interval starts at 2, which falls within the first interval's range of 1 to 3. When merged, they become [1, 6].

The goal is to produce the smallest set of intervals that accounts for all the ranges in the input, with no two output intervals sharing any common point.

Examples

Example 1

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

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

Explanation: The intervals [1, 3] and [2, 6] overlap because 2 falls within the range [1, 3]. When we merge them, the combined range stretches from 1 (the smaller start) to 6 (the larger end), giving us [1, 6]. The remaining intervals [8, 10] and [15, 18] do not overlap with anything, so they stay unchanged.

Example 2

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

Output: [[1, 5]]

Explanation: The intervals [1, 4] and [4, 5] share the point 4 — the end of the first interval equals the start of the second. This counts as overlapping, so they merge into [1, 5].

Example 3

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

Output: [[1, 7]]

Explanation: Even though the intervals are not given in sorted order, [1, 4] and [4, 7] overlap at the point 4 and merge into [1, 7]. The input order does not affect the final result.

Constraints

  • 1 ≤ intervals.length ≤ 10^4
  • intervals[i].length == 2
  • 0 ≤ start_i ≤ end_i ≤ 10^4

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to compare every interval with every other interval and check if they overlap. If two intervals overlap, we merge them into a single larger interval and then repeat the process until no more merges are possible.

Think of it like organizing a messy pile of sticky notes on a timeline. You pick up the first note, then check it against every other note. If any two notes share timeline space, you combine them into one longer note. You keep doing this until no notes overlap anymore.

The challenge with this approach is that merging two intervals might create a new interval that now overlaps with something it previously didn't. So you need to keep going through the list until a full pass produces no merges — meaning the process has stabilized.

Step-by-Step Explanation

Let's trace through with intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]:

First, we sort the intervals by their start values: [[1, 3], [2, 6], [8, 10], [15, 18]] (already sorted in this case).

Step 1: Start with the first interval [1, 3]. Set current_start = 1, current_end = 3.

Step 2: Compare [1, 3] with the next interval [2, 6]. Does the start of [2, 6] (which is 2) fall within [1, 3]? Yes, 2 ≤ 3. They overlap.

Step 3: Merge them: new end = max(3, 6) = 6. Current merged interval becomes [1, 6].

Step 4: Now scan forward to check if [8, 10] overlaps with [1, 6]. Does 8 ≤ 6? No. So [1, 6] is complete — add it to the result.

Step 5: Move to [8, 10]. Compare with [15, 18]. Does 15 ≤ 10? No. So [8, 10] is complete — add it to the result.

Step 6: [15, 18] has no more intervals to compare with. Add it to the result.

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

Brute Force — Comparing All Interval Pairs — Watch how we pick each interval, scan all remaining intervals for overlaps, and merge when the start of the next interval falls within the current interval's range.

Algorithm

  1. Sort all intervals by their start values
  2. For each interval, set it as the current interval
  3. Compare the current interval with every subsequent interval:
    • If the next interval's start ≤ current interval's end, they overlap
    • Merge by updating current end = max(current end, next interval's end)
    • Mark the next interval as consumed
  4. When no more overlaps are found, add the current merged interval to the result
  5. Repeat from the next unconsumed interval
  6. Return the result list

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> result;

        for (int i = 0; i < n; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];

            // Skip intervals already merged
            if (!result.empty() && result.back()[1] >= end)
                continue;

            // Extend end as far as possible
            for (int j = i + 1; j < n; j++) {
                if (intervals[j][0] <= end)
                    end = max(end, intervals[j][1]);
            }
            result.push_back({start, end});
        }
        return result;
    }
};
class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort()
        result = []

        for i in range(len(intervals)):
            start = intervals[i][0]
            end = intervals[i][1]

            # Skip intervals already merged
            if result and result[-1][1] >= end:
                continue

            # Extend end as far as possible
            for j in range(i + 1, len(intervals)):
                if intervals[j][0] <= end:
                    end = max(end, intervals[j][1])

            result.append([start, end])

        return result
import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> result = new ArrayList<>();
        int n = intervals.length;

        for (int i = 0; i < n; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];

            // Skip intervals already merged
            if (!result.isEmpty() && result.get(result.size() - 1)[1] >= end)
                continue;

            // Extend end as far as possible
            for (int j = i + 1; j < n; j++) {
                if (intervals[j][0] <= end)
                    end = Math.max(end, intervals[j][1]);
            }
            result.add(new int[]{start, end});
        }

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

Complexity Analysis

Time Complexity: O(n²)

Sorting takes O(n log n). After sorting, for each interval we potentially scan all remaining intervals in the inner loop. In the worst case (e.g., no overlaps), the outer loop runs n times and the inner loop also runs up to n times for each iteration, giving O(n²) for the scanning phase. The dominant term is O(n²).

Space Complexity: O(n)

We store the merged intervals in a result list. In the worst case (no merges), this holds all n original intervals, requiring O(n) space. The sorting may also use O(log n) stack space depending on the implementation.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity due to the nested loop — for each interval, we scan all subsequent intervals to find overlaps. With n up to 10^4, this means up to 5×10^7 operations, which is borderline for typical time limits.

The key inefficiency is that after sorting, once we encounter an interval whose start is beyond our current merged end, we know all further intervals will also be beyond it (because they are sorted). There is no need to keep scanning — we can stop the inner loop immediately.

This insight means we can process each interval exactly once in a single pass after sorting, reducing the time from O(n²) to O(n log n), with the sorting step being the bottleneck.

Optimal Approach - Sorting with Single Pass

Intuition

The key insight is that if we sort all intervals by their start times, overlapping intervals will be adjacent to each other in the sorted order. This means we only need to compare each interval with the one immediately before it (or more precisely, with the last interval we added to our result).

Imagine you are placing colored strips of tape on a number line from left to right. After sorting by where each strip begins, you lay down the first strip. For every subsequent strip, you only need to check: does this new strip start before the previous one ends? If yes, extend the previous strip. If no, place it as a separate strip.

This works because sorting guarantees that no future strip can start earlier than the current one. So once a gap appears between the current merged strip and the next one, that gap will never be filled by a later interval.

The process becomes a simple linear scan: maintain the last merged interval, and for each new interval, either extend the last one or start a new one.

Step-by-Step Explanation

Let's trace through with intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]:

Step 1: Sort intervals by start value. They are already sorted: [[1, 3], [2, 6], [8, 10], [15, 18]].

Step 2: Add the first interval [1, 3] to the result. Result = [[1, 3]].

Step 3: Process [2, 6]. Compare its start (2) with the end of the last result interval (3). Is 2 ≤ 3? YES — overlap detected.

Step 4: Merge: update the last result interval's end to max(3, 6) = 6. Result = [[1, 6]].

Step 5: Process [8, 10]. Compare its start (8) with the end of the last result interval (6). Is 8 ≤ 6? NO — no overlap.

Step 6: No overlap, so add [8, 10] as a new interval. Result = [[1, 6], [8, 10]].

Step 7: Process [15, 18]. Compare its start (15) with the end of the last result interval (10). Is 15 ≤ 10? NO — no overlap.

Step 8: No overlap, so add [15, 18] as a new interval. Result = [[1, 6], [8, 10], [15, 18]].

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

Optimal Approach — Sort and Merge in One Pass — Watch how sorting intervals by start time lets us merge overlapping intervals in a single left-to-right pass, comparing each interval only with the last merged result.

Algorithm

  1. Sort the intervals array by each interval's start value
  2. Initialize a result list and add the first interval to it
  3. For each remaining interval:
    • If the current interval's start ≤ the last result interval's end, they overlap:
      • Update the last result interval's end to max(last end, current end)
    • Otherwise, no overlap:
      • Add the current interval as a new entry in the result
  4. Return the result list

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> result;
        result.push_back(intervals[0]);

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

            if (curr[0] <= last[1]) {
                // Overlap: extend the last merged interval
                last[1] = max(last[1], curr[1]);
            } else {
                // No overlap: start a new interval
                result.push_back(curr);
            }
        }

        return result;
    }
};
class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort()
        result = [intervals[0]]

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

            if curr[0] <= last[1]:
                # Overlap: extend the last merged interval
                last[1] = max(last[1], curr[1])
            else:
                # No overlap: start a new interval
                result.append(curr)

        return result
import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> 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: extend the last merged interval
                last[1] = Math.max(last[1], curr[1]);
            } else {
                // No overlap: start a new interval
                result.add(curr);
            }
        }

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

Complexity Analysis

Time Complexity: O(n log n)

The dominant operation is the initial sort, which takes O(n log n). After sorting, we traverse the intervals exactly once in a single pass — each interval is visited once and either merged or added to the result in O(1) time. So the total is O(n log n) + O(n) = O(n log n).

Space Complexity: O(n)

The result list can hold up to n intervals in the worst case (when no intervals overlap). The sorting step may also use O(log n) auxiliary space. Overall space usage is O(n).

This is the best possible time complexity for this problem because any algorithm that distinguishes between overlapping and non-overlapping intervals must at minimum compare them, and without sorting, this requires O(n²) comparisons. Sorting in O(n log n) enables the linear-time merge pass.