Merge Intervals

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

Language Selection

Choose your preferred programming language

Showing: Python

Merge Intervals

Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], 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: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping since they share endpoint 4.

Example 3:

Input: intervals = [[1,4],[0,4]]
Output: [[0,4]]
Explanation: After sorting by start, [0,4] comes first and [1,4] is contained within it.

Example 4:

Input: intervals = [[1,4],[0,2],[3,5]]
Output: [[0,5]]
Explanation: All three intervals overlap transitively: [0,2] overlaps [1,4], and [1,4] overlaps [3,5]. They merge into [0,5].

Constraints

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

Approach 1: Sort by Start Time + Linear Merge (Optimal)

Algorithm Explanation

The key insight is that if we sort intervals by their start time, overlapping intervals will be adjacent. We then make a single pass to merge them.

Steps:

  1. Sort the intervals by their start value.
  2. Initialize a result list with the first interval.
  3. For each subsequent interval:
    • If it overlaps with the last interval in the result (i.e., its start is less than or equal to the last interval’s end), merge them by updating the end to the maximum of both ends.
    • Otherwise, append the interval to the result as a new non-overlapping interval.
  4. Return the result.

Two intervals [a, b] and [c, d] overlap when c <= b (assuming a <= c after sorting).

Implementation

Python:

def merge(intervals):
    """
    Merge overlapping intervals after sorting by start time.
    Time: O(n log n)
    Space: O(n) for the output
    """
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

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

        if current[0] <= last[1]:
            # Overlapping: extend the end of the last merged interval
            last[1] = max(last[1], current[1])
        else:
            # Non-overlapping: add new interval
            merged.append(current)

    return merged

Java:

import java.util.*;

class Solution {
    /**
     * Merge overlapping intervals after sorting by start time.
     * Time: O(n log n)
     * Space: O(n) for the output
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

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

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

            if (current[0] <= last[1]) {
                // Overlapping: extend the end
                last[1] = Math.max(last[1], current[1]);
            } else {
                // Non-overlapping: add new interval
                merged.add(current);
            }
        }

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

Go:

import "sort"

// merge merges overlapping intervals after sorting by start time.
// Time: O(n log n), Space: O(n)
func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := [][]int{intervals[0]}

    for i := 1; i < len(intervals); i++ {
        last := merged[len(merged)-1]
        current := intervals[i]

        if current[0] <= last[1] {
            // Overlapping: extend the end
            if current[1] > last[1] {
                last[1] = current[1]
            }
        } else {
            // Non-overlapping: add new interval
            merged = append(merged, current)
        }
    }

    return merged
}

JavaScript:

/**
 * Merge overlapping intervals after sorting by start time.
 * Time: O(n log n)
 * Space: O(n) for the output
 */
function merge(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);

    const merged = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const last = merged[merged.length - 1];
        const current = intervals[i];

        if (current[0] <= last[1]) {
            // Overlapping: extend the end
            last[1] = Math.max(last[1], current[1]);
        } else {
            // Non-overlapping: add new interval
            merged.push(current);
        }
    }

    return merged;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Merge overlapping intervals after sorting by start time.
    /// Time: O(n log n)
    /// Space: O(n) for the output
    /// </summary>
    public int[][] Merge(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

        var merged = new List<int[]>();
        merged.Add(intervals[0]);

        for (int i = 1; i < intervals.Length; i++) {
            int[] last = merged[merged.Count - 1];
            int[] current = intervals[i];

            if (current[0] <= last[1]) {
                // Overlapping: extend the end
                last[1] = Math.Max(last[1], current[1]);
            } else {
                // Non-overlapping: add new interval
                merged.Add(current);
            }
        }

        return merged.ToArray();
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) – dominated by the sort. The subsequent linear scan is O(n).
  • Space Complexity: O(n) – for the output list. Some languages may use O(log n) additional space for sorting.

Approach 2: Connected Components (Brute Force)

Algorithm Explanation

This approach models the problem as a graph. Each interval is a node, and two nodes are connected by an edge if their intervals overlap. A set of intervals that must be merged together forms a connected component in this graph. The merged interval for each component is [min(starts), max(ends)].

While this approach is less efficient than sorting, it illustrates the underlying structure of the problem and is useful for understanding why sorting works.

Steps:

  1. Build an adjacency list: for every pair of intervals, check if they overlap.
  2. Run BFS or DFS to find connected components.
  3. For each connected component, the merged interval is [min of all starts, max of all ends].

Implementation

Python:

from collections import defaultdict, deque

def merge_connected(intervals):
    """
    Merge overlapping intervals using connected components (graph BFS).
    Time: O(n^2)
    Space: O(n^2)
    """
    n = len(intervals)
    if n <= 1:
        return intervals

    def overlaps(a, b):
        return a[0] <= b[1] and b[0] <= a[1]

    # Build adjacency list
    graph = defaultdict(list)
    for i in range(n):
        for j in range(i + 1, n):
            if overlaps(intervals[i], intervals[j]):
                graph[i].append(j)
                graph[j].append(i)

    # BFS to find connected components
    visited = [False] * n
    result = []

    for i in range(n):
        if visited[i]:
            continue
        # BFS from node i
        queue = deque([i])
        visited[i] = True
        comp_min = intervals[i][0]
        comp_max = intervals[i][1]

        while queue:
            node = queue.popleft()
            comp_min = min(comp_min, intervals[node][0])
            comp_max = max(comp_max, intervals[node][1])
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

        result.append([comp_min, comp_max])

    return result

Java:

import java.util.*;

class Solution {
    /**
     * Merge overlapping intervals using connected components (graph BFS).
     * Time: O(n^2)
     * Space: O(n^2)
     */
    public int[][] mergeConnected(int[][] intervals) {
        int n = intervals.length;
        if (n <= 1) return intervals;

        // Build adjacency list
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (intervals[i][0] <= intervals[j][1] &&
                    intervals[j][0] <= intervals[i][1]) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }
            }
        }

        // BFS to find connected components
        boolean[] visited = new boolean[n];
        List<int[]> result = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            visited[i] = true;
            int compMin = intervals[i][0];
            int compMax = intervals[i][1];

            while (!queue.isEmpty()) {
                int node = queue.poll();
                compMin = Math.min(compMin, intervals[node][0]);
                compMax = Math.max(compMax, intervals[node][1]);
                for (int neighbor : graph.get(node)) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.offer(neighbor);
                    }
                }
            }

            result.add(new int[]{compMin, compMax});
        }

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

Go:

// mergeConnected merges overlapping intervals using connected components (BFS).
// Time: O(n^2), Space: O(n^2)
func mergeConnected(intervals [][]int) [][]int {
    n := len(intervals)
    if n <= 1 {
        return intervals
    }

    // Build adjacency list
    graph := make([][]int, n)
    for i := 0; i < n; i++ {
        graph[i] = []int{}
    }
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if intervals[i][0] <= intervals[j][1] &&
                intervals[j][0] <= intervals[i][1] {
                graph[i] = append(graph[i], j)
                graph[j] = append(graph[j], i)
            }
        }
    }

    // BFS to find connected components
    visited := make([]bool, n)
    var result [][]int

    for i := 0; i < n; i++ {
        if visited[i] {
            continue
        }
        queue := []int{i}
        visited[i] = true
        compMin := intervals[i][0]
        compMax := intervals[i][1]

        for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]
            if intervals[node][0] < compMin {
                compMin = intervals[node][0]
            }
            if intervals[node][1] > compMax {
                compMax = intervals[node][1]
            }
            for _, neighbor := range graph[node] {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }

        result = append(result, []int{compMin, compMax})
    }

    return result
}

JavaScript:

/**
 * Merge overlapping intervals using connected components (graph BFS).
 * Time: O(n^2)
 * Space: O(n^2)
 */
function mergeConnected(intervals) {
    const n = intervals.length;
    if (n <= 1) return intervals;

    function overlaps(a, b) {
        return a[0] <= b[1] && b[0] <= a[1];
    }

    // Build adjacency list
    const graph = Array.from({ length: n }, () => []);
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (overlaps(intervals[i], intervals[j])) {
                graph[i].push(j);
                graph[j].push(i);
            }
        }
    }

    // BFS to find connected components
    const visited = new Array(n).fill(false);
    const result = [];

    for (let i = 0; i < n; i++) {
        if (visited[i]) continue;

        const queue = [i];
        visited[i] = true;
        let compMin = intervals[i][0];
        let compMax = intervals[i][1];

        while (queue.length > 0) {
            const node = queue.shift();
            compMin = Math.min(compMin, intervals[node][0]);
            compMax = Math.max(compMax, intervals[node][1]);
            for (const neighbor of graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }

        result.push([compMin, compMax]);
    }

    return result;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Merge overlapping intervals using connected components (graph BFS).
    /// Time: O(n^2)
    /// Space: O(n^2)
    /// </summary>
    public int[][] MergeConnected(int[][] intervals) {
        int n = intervals.Length;
        if (n <= 1) return intervals;

        // Build adjacency list
        var graph = new List<List<int>>();
        for (int i = 0; i < n; i++) graph.Add(new List<int>());

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (intervals[i][0] <= intervals[j][1] &&
                    intervals[j][0] <= intervals[i][1]) {
                    graph[i].Add(j);
                    graph[j].Add(i);
                }
            }
        }

        // BFS to find connected components
        bool[] visited = new bool[n];
        var result = new List<int[]>();

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;

            var queue = new Queue<int>();
            queue.Enqueue(i);
            visited[i] = true;
            int compMin = intervals[i][0];
            int compMax = intervals[i][1];

            while (queue.Count > 0) {
                int node = queue.Dequeue();
                compMin = Math.Min(compMin, intervals[node][0]);
                compMax = Math.Max(compMax, intervals[node][1]);
                foreach (int neighbor in graph[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.Enqueue(neighbor);
                    }
                }
            }

            result.Add(new int[] { compMin, compMax });
        }

        return result.ToArray();
    }
}

Complexity Analysis

  • Time Complexity: O(n^2) – checking all pairs to build the graph.
  • Space Complexity: O(n^2) – storing the adjacency list in the worst case.

Trade-offs:

  • This approach is conceptually clear and shows the graph structure of the problem.
  • It is too slow for large inputs but helps explain why sorting works: sorting ensures that transitive overlaps are handled in order, eliminating the need to check all pairs.

Key Insights

  1. Sorting Is the Key: Once intervals are sorted by start time, overlapping intervals are always adjacent. This transforms the problem into a simple linear scan.
  2. Overlap Condition: After sorting, interval B overlaps with the current merged interval A if and only if B.start <= A.end. This single comparison drives the merge logic.
  3. Greedy Extension: When merging, we always take the maximum end time: A.end = max(A.end, B.end). This handles cases where one interval is completely contained within another.
  4. Transitive Overlaps: Intervals [1,3] and [4,6] do not overlap directly, but if [2,5] exists, all three merge into [1,6]. Sorting guarantees that such transitive chains are discovered left-to-right without needing a graph.
  5. In-Place vs Output: The algorithm builds a new output list. Merging in-place within the sorted array is possible but trickier and not more efficient since the output itself requires O(n) space.
  6. Stability: The sort only needs to compare start values. Intervals with the same start value can be in any relative order because the merge step handles them correctly (the one with the larger end simply extends the merged interval).

Edge Cases

  1. Single Interval: [[5,7]] – nothing to merge, return as-is.
  2. No Overlaps: [[1,2],[4,5],[7,8]] – all intervals are disjoint.
  3. All Overlapping: [[1,10],[2,5],[3,7]] – everything merges into a single interval [1,10].
  4. Touching Endpoints: [[1,4],[4,5]] – these are considered overlapping and merge to [1,5].
  5. Contained Intervals: [[1,10],[2,3],[4,5]] – smaller intervals are fully contained; result is [1,10].
  6. Unsorted Input: [[3,4],[1,2]] – the sort handles this correctly.
  7. Identical Intervals: [[1,3],[1,3]] – duplicate intervals merge into one.
  8. Same Start Different Ends: [[1,3],[1,6]] – merge to [1,6].

Test Cases

def test_merge():
    # Test case 1: Standard overlapping
    assert merge([[1, 3], [2, 6], [8, 10], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]

    # Test case 2: Touching endpoints
    assert merge([[1, 4], [4, 5]]) == [[1, 5]]

    # Test case 3: Single interval
    assert merge([[5, 7]]) == [[5, 7]]

    # Test case 4: No overlaps
    assert merge([[1, 2], [4, 5], [7, 8]]) == [[1, 2], [4, 5], [7, 8]]

    # Test case 5: All merge into one
    assert merge([[1, 10], [2, 5], [3, 7]]) == [[1, 10]]

    # Test case 6: Unsorted input
    assert merge([[3, 4], [1, 2], [2, 3]]) == [[1, 4]]

    # Test case 7: Contained intervals
    assert merge([[1, 10], [2, 3], [4, 5], [6, 7]]) == [[1, 10]]

    # Test case 8: Identical intervals
    assert merge([[1, 3], [1, 3]]) == [[1, 3]]

    # Test case 9: Reverse sorted
    assert merge([[8, 10], [1, 3], [2, 6], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]

    # Test case 10: Transitive overlap chain
    assert merge([[1, 3], [2, 5], [4, 8]]) == [[1, 8]]

    # Test case 11: Same start different ends
    assert merge([[1, 3], [1, 6]]) == [[1, 6]]

    print("All tests passed!")

test_merge()

Common Mistakes

  1. Forgetting to Sort: Attempting to merge without sorting first leads to missed overlaps when intervals are not in order. Sorting by start time is essential.
  2. Wrong Overlap Check: Using current[0] < last[1] (strict less-than) instead of current[0] <= last[1]. Intervals that touch at a point (e.g., [1,4] and [4,5]) should be merged.
  3. Not Taking Max End: Setting last[1] = current[1] instead of last[1] = max(last[1], current[1]). This fails when the current interval is contained within the last merged interval (e.g., merging [1,10] with [2,5] should keep end as 10, not 5).
  4. Modifying While Iterating: Trying to remove elements from the original list during iteration. It is cleaner to build a new result list.
  5. Empty Input: Not handling the edge case of an empty intervals array. The constraints guarantee at least one interval, but defensive programming is good practice.
  6. Sorting by End Instead of Start: Sorting by end time does not guarantee adjacent overlaps and leads to incorrect results.

Interview Tips

  1. Start with the Key Insight: Immediately state that sorting by start time makes overlapping intervals adjacent, simplifying the problem to a linear scan.
  2. Walk Through an Example: Use [[1,3],[2,6],[8,10],[15,18]] and trace through the sort and merge steps on the whiteboard.
  3. Mention Complexity Clearly: The bottleneck is the O(n log n) sort; the merge is O(n). Overall: O(n log n) time, O(n) space.
  4. Discuss Related Problems: Mention Insert Interval (LeetCode #57), Meeting Rooms (LeetCode #252), and Meeting Rooms II (LeetCode #253) as natural follow-ups.
  5. Consider Follow-Ups: What if intervals arrive in a stream? (Use a balanced BST or interval tree.) What if the input is already sorted? (Then the merge is just O(n).) What if you need to count the number of overlapping groups without merging? (Use the connected components approach.)