Merge Intervals

Problem Statement

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.

What to notice first

• Two intervals [a, b] and [c, d] overlap if c <= b.
• After merging, the result should contain non-overlapping intervals in sorted order.
• A simple sort-and-scan approach is often optimal for this problem.

Examples

Input	Output	Explanation
[[1,3],[2,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]	[1,3] and [2,6] overlap, merge to [1,6].
[[1,4],[4,5]]	[[1,5]]	[1,4] and [4,5] overlap at the boundary.
[[1,2],[1,2]]	[[1,2]]	Identical intervals merge to one.

Constraints

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

Where this pattern appears

• Calendar event merging — Scheduling systems consolidating overlapping time blocks from multiple calendars or shared resources.
• Resource allocation — Server and container orchestration merging time windows of resource availability or maintenance windows.
• Time slot consolidation — Educational or booking systems merging adjacent or overlapping appointment slots into contiguous blocks.
• Meeting scheduling — Calendar applications automatically merging or detecting conflicts between overlapping meeting times across participants.

Complexity Comparison

Approach	Time	Space	Best When
Sort and Merge	O(n log n)	O(1)	Optimal — simplest and fastest
Heap	O(n log n)	O(n)	Alternative structure

Which approach should you learn first?

• Pick Sort and Merge for the optimal interview solution — it is intuitive and efficient.
• Pick Heap if you want to practice heap-based interval handling.

Optimal

Sort and Merge

O(n log n) time · O(1) space

Heap-based

Heap

O(n log n) time · O(n) space

Approach 1: Sort and Merge (Recommended)

★ Recommended

Sort intervals by start time, then iterate through and merge overlapping intervals by updating the end time when an overlap is detected.

⏱ Time O(n log n) Sorting dominant 💾 Space O(1) Constant

Solution Code

Python

merge_intervals_sort_and_merge.py

from typing import List

def merge(intervals: List[List[int]]) -> List[List[int]]:
    """Sort and merge approach: O(n log n) time, O(n) space"""
    if not intervals:
        return []
    intervals.sort()
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))

C++

merge_intervals_sort_and_merge.cpp

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

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] <= merged.back()[1]) {
            merged.back()[1] = max(merged.back()[1], intervals[i][1]);
        } else {
            merged.push_back(intervals[i]);
        }
    }
    return merged;
}

Java

merge_intervals_sort_and_merge.java

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

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][0];

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

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

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= current[1]) {
                current[1] = Math.max(current[1], intervals[i][1]);
            } else {
                merged.add(current);
                current = intervals[i];
            }
        }
        merged.add(current);

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

int[][] result = new Solution().merge(new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}});
for (int[] interval : result) {
    System.out.println(Arrays.toString(interval));
}

JavaScript

merge_intervals_sort_and_merge.js

function merge(intervals) {
    if (!intervals.length) return [];
    intervals.sort((a, b) => a[0] - b[0]);
    const merged = [intervals[0]];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= merged[merged.length - 1][1]) {
            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], intervals[i][1]);
        } else {
            merged.push(intervals[i]);
        }
    }
    return merged;
}
module.exports = merge;

Rust

merge_intervals_sort_and_merge.rs

pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    if intervals.is_empty() { return vec![]; }
    intervals.sort_by_key(|a| a[0]);
    let mut merged = vec![intervals[0].clone()];
    for interval in &intervals[1..] {
        let last = merged.last_mut().unwrap();
        if interval[0] <= last[1] {
            last[1] = last[1].max(interval[1]);
        } else {
            merged.push(interval.clone());
        }
    }
    merged
}

Go

merge_intervals_sort_and_merge.go

package main

import "sort"

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 { return [][]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]
        if intervals[i][0] <= (*last)[1] {
            (*last)[1] = max((*last)[1], intervals[i][1])
        } else {
            merged = append(merged, intervals[i])
        }
    }
    return merged
}

func max(a, b int) int { if a > b { return a }; return b }

Approach 2: Heap / Priority Queue

🎯 Interview Favourite

Use a min-heap to extract intervals in order by start time and merge them dynamically.

⏱ Time O(n log n) Heap operations 💾 Space O(n) Heap storage

Solution Code

Python

merge_intervals_heap.py

from typing import List
import heapq

def merge(intervals: List[List[int]]) -> List[List[int]]:
    """Heap approach: O(n log n) time, O(n) space"""
    if not intervals:
        return []
    heap = []
    for start, end in intervals:
        heapq.heappush(heap, (start, end))
    merged = []
    while heap:
        start, end = heapq.heappop(heap)
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge([[1, 3], [2, 6], [8, 10]]))

C++

merge_intervals_heap.cpp

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

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (auto& interval : intervals) {
        pq.push({interval[0], interval[1]});
    }
    vector<vector<int>> merged;
    while (!pq.empty()) {
        auto [start, end] = pq.top(); pq.pop();
        if (!merged.empty() && start <= merged.back()[1]) {
            merged.back()[1] = max(merged.back()[1], end);
        } else {
            merged.push_back({start, end});
        }
    }
    return merged;
}

Java

merge_intervals_heap.java

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][0];

        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int[] interval : intervals) {
            heap.offer(interval);
        }

        List<int[]> merged = new ArrayList<>();
        while (!heap.isEmpty()) {
            int[] current = heap.poll();
            if (!merged.isEmpty() && current[0] <= merged.get(merged.size() - 1)[1]) {
                int[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], current[1]);
            } else {
                merged.add(current);
            }
        }

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

int[][] result = new Solution().merge(new int[][]{{1, 3}, {2, 6}, {8, 10}});
for (int[] interval : result) {
    System.out.println(java.util.Arrays.toString(interval));
}

JavaScript

merge_intervals_heap.js

function merge(intervals) {
    const pq = intervals.sort((a, b) => a[0] - b[0]);
    const merged = [pq.shift()];
    for (let interval of pq) {
        if (interval[0] <= merged[merged.length - 1][1]) {
            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
        } else {
            merged.push(interval);
        }
    }
    return merged;
}
module.exports = merge;

Rust

merge_intervals_heap.rs

pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    if intervals.is_empty() { return vec![]; }
    let mut sorted = intervals;
    sorted.sort_by_key(|a| a[0]);
    let mut merged = vec![sorted[0].clone()];
    for interval in &sorted[1..] {
        let last = merged.last_mut().unwrap();
        if interval[0] <= last[1] {
            last[1] = last[1].max(interval[1]);
        } else {
            merged.push(interval.clone());
        }
    }
    merged
}

Go

merge_intervals_heap.go

package main

import "sort"

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 { return [][]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]
        if intervals[i][0] <= (*last)[1] {
            (*last)[1] = max((*last)[1], intervals[i][1])
        } else {
            merged = append(merged, intervals[i])
        }
    }
    return merged
}

func max(a, b int) int { if a > b { return a }; return b }

Common mistakes

Watch for these pitfalls

• Forgetting to sort intervals before merging.
• Using < instead of <= when checking for overlaps.
• Not updating the end of the current interval when merging.
• Handling edge cases like adjacent intervals [1,2] and [2,3].

Related Problems

• Insert Interval ↗ Medium #57
• Summary Ranges ↗ Easy #228
• Non-overlapping Intervals ↗ Medium #435

Interview Tips

Key points to discuss

• Sort first — Sorting by start time is the crucial insight that makes merging linear in the sorted pass.
• Overlap detection — Two intervals overlap if the next start is within or at the end of the current interval: next.start <= current.end.
• Why Sort and Merge is optimal — Both approaches are O(n log n) due to sorting, but Sort and Merge uses O(1) space, making it superior.
• Heap alternative — If intervals arrive in a stream, a heap lets you process them online without sorting the entire input first.
• Edge cases: Adjacent intervals like [1,2] and [2,3] (should merge), duplicate intervals, single interval.
• Follow-up: “What if intervals arrive in a stream?” → Use a heap-based approach or balanced tree for dynamic merging.