What happens if you not sorting intervals before merging?

Incorrect merges or missed overlaps Fix: Always sort intervals by start time before merging

What happens if you modifying the list while iterating without adjusting indices?

Index errors or skipping intervals Fix: Use careful index management or iterate backwards when removing elements

What happens if you not updating the end time correctly when merging?

Merged intervals are incorrect or incomplete Fix: Update the end time to the max of overlapping intervals

Interview PrepintervalsmediumFacebookAmazonGoogleMicrosoftBloomberg

Merge Intervals

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

🎯

Merge Intervals

mediumINTERVALSFacebookAmazonGoogle

Imagine you have a calendar with multiple booked time slots, and you want to combine overlapping meetings to see your free time clearly.

💡 This problem is about combining overlapping intervals into one continuous interval. Beginners often struggle because they don't realize sorting the intervals by start time simplifies merging, and they try to compare every interval with every other, leading to inefficient solutions.

📋

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.

1 ≤ intervals.length ≤ 10^5intervals[i].length == 20 ≤ start_i ≤ end_i ≤ 10^9

💡

Example

Input"[[1,3],[2,6],[8,10],[15,18]]"

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

Intervals [1,3] and [2,6] overlap and are merged into [1,6]. The others do not overlap.

Single interval → output is the same single interval
All intervals non-overlapping → output is the same as input
All intervals overlapping → output is one merged interval
Intervals with same start and end points → merged correctly

⚠️

Common Mistakes

Not sorting intervals before merging

Incorrect merges or missed overlaps

✅ Always sort intervals by start time before merging

Modifying the list while iterating without adjusting indices

Index errors or skipping intervals

✅ Use careful index management or iterate backwards when removing elements

Not updating the end time correctly when merging

Merged intervals are incorrect or incomplete

✅ Update the end time to the max of overlapping intervals

Returning the original intervals array without slicing after in-place merge

Extra intervals remain in output, causing wrong results

✅ Return only the portion of the array up to the last merged index

🧠

Brute Force (Nested Loops Checking Overlaps)

💡 This approach exists to understand the problem deeply by checking every pair of intervals for overlap. It is inefficient but helps grasp the merging concept.

Intuition

Compare each interval with every other to check if they overlap, merge them if they do, and repeat until no more merges are possible.

Algorithm

Initialize a list to hold merged intervals.
For each interval, compare it with every other interval to check for overlap.
If two intervals overlap, merge them into one interval.
Repeat the process until no intervals can be merged further.

💡 This algorithm is hard to see as efficient because it involves repeated comparisons and merges, which can be confusing at first.

</>

Code

def merge(intervals):
    merged = []
    intervals = intervals[:]  # copy to avoid modifying input
    while intervals:
        current = intervals.pop(0)
        i = 0
        while i < len(intervals):
            if current[1] >= intervals[i][0] and intervals[i][1] >= current[0]:
                current = [min(current[0], intervals[i][0]), max(current[1], intervals[i][1])]
                intervals.pop(i)
            else:
                i += 1
        merged.append(current)
    return merged

# Driver code
if __name__ == '__main__':
    intervals = [[1,3],[2,6],[8,10],[15,18]]
    print(merge(intervals))

Line Notes

merged = []Initialize list to store merged intervals to accumulate results.

intervals = intervals[:] # copy to avoid modifying inputCopy input to avoid side effects on original data.

while intervals:Process intervals until all have been merged and removed.

current = intervals.pop(0)Pick the first interval to compare and merge with others.

while i < len(intervals):Iterate over remaining intervals to check for overlaps.

if current[1] >= intervals[i][0] and intervals[i][1] >= current[0]:Check if current interval overlaps with intervals[i].

current = [min(current[0], intervals[i][0]), max(current[1], intervals[i][1])]Merge overlapping intervals by updating start and end.

intervals.pop(i)Remove merged interval to avoid reprocessing it.

else: i += 1Move to next interval if no overlap found.

merged.append(current)Add the fully merged interval to the result list.

import java.util.*;
public class MergeIntervals {
    public static List<int[]> merge(int[][] intervals) {
        List<int[]> merged = new ArrayList<>();
        List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
        while (!list.isEmpty()) {
            int[] current = list.remove(0);
            int i = 0;
            while (i < list.size()) {
                int[] interval = list.get(i);
                if (current[1] >= interval[0] && interval[1] >= current[0]) {
                    current[0] = Math.min(current[0], interval[0]);
                    current[1] = Math.max(current[1], interval[1]);
                    list.remove(i);
                } else {
                    i++;
                }
            }
            merged.add(current);
        }
        return merged;
    }
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        List<int[]> result = merge(intervals);
        for (int[] interval : result) {
            System.out.println("[" + interval[0] + "," + interval[1] + "]");
        }
    }
}

Line Notes

List<int[]> merged = new ArrayList<>();Initialize list to store merged intervals.

List<int[]> list = new ArrayList<>(Arrays.asList(intervals));Copy input array to a modifiable list.

while (!list.isEmpty()) {Process intervals until all are merged and removed.

int[] current = list.remove(0);Pick first interval to compare and merge.

while (i < list.size()) {Iterate over remaining intervals to check for overlaps.

if (current[1] >= interval[0] && interval[1] >= current[0]) {Check if intervals overlap.

current[0] = Math.min(current[0], interval[0]);Update start of merged interval.

current[1] = Math.max(current[1], interval[1]);Update end of merged interval.

list.remove(i);Remove merged interval to avoid reprocessing.

else { i++; }Move to next interval if no overlap.

merged.add(current);Add merged interval to result list.

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

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> merged;
    vector<vector<int>> list = intervals;
    while (!list.empty()) {
        vector<int> current = list[0];
        list.erase(list.begin());
        for (int i = 0; i < (int)list.size();) {
            if (current[1] >= list[i][0] && list[i][1] >= current[0]) {
                current[0] = min(current[0], list[i][0]);
                current[1] = max(current[1], list[i][1]);
                list.erase(list.begin() + i);
            } else {
                i++;
            }
        }
        merged.push_back(current);
    }
    return merged;
}

int main() {
    vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
    vector<vector<int>> result = merge(intervals);
    for (auto &interval : result) {
        cout << "[" << interval[0] << "," << interval[1] << "]\n";
    }
    return 0;
}

Line Notes

vector<vector<int>> merged;Initialize vector to store merged intervals.

vector<vector<int>> list = intervals;Copy input intervals for modification.

while (!list.empty()) {Process intervals until all merged.

vector<int> current = list[0];Pick first interval to compare and merge.

list.erase(list.begin());Remove picked interval from list.

for (int i = 0; i < (int)list.size();) {Iterate over remaining intervals.

if (current[1] >= list[i][0] && list[i][1] >= current[0]) {Check if intervals overlap.

current[0] = min(current[0], list[i][0]);Update start of merged interval.

current[1] = max(current[1], list[i][1]);Update end of merged interval.

list.erase(list.begin() + i);Remove merged interval to avoid reprocessing.

else { i++; }Move to next interval if no overlap.

merged.push_back(current);Add merged interval to result.

function merge(intervals) {
    let merged = [];
    intervals = intervals.slice();
    while (intervals.length > 0) {
        let current = intervals.shift();
        let i = 0;
        while (i < intervals.length) {
            if (current[1] >= intervals[i][0] && intervals[i][1] >= current[0]) {
                current = [Math.min(current[0], intervals[i][0]), Math.max(current[1], intervals[i][1])];
                intervals.splice(i, 1);
            } else {
                i++;
            }
        }
        merged.push(current);
    }
    return merged;
}

// Driver code
console.log(merge([[1,3],[2,6],[8,10],[15,18]]));

Line Notes

let merged = [];Initialize array to store merged intervals.

intervals = intervals.slice();Copy input to avoid mutating original array.

while (intervals.length > 0) {Process intervals until all merged.

let current = intervals.shift();Pick first interval to compare and merge.

while (i < intervals.length) {Iterate over remaining intervals.

if (current[1] >= intervals[i][0] && intervals[i][1] >= current[0]) {Check if intervals overlap.

current = [Math.min(current[0], intervals[i][0]), Math.max(current[1], intervals[i][1])];Merge overlapping intervals.

intervals.splice(i, 1);Remove merged interval to avoid reprocessing.

else { i++; }Move to next interval if no overlap.

merged.push(current);Add merged interval to result.

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Each interval is compared with every other interval, leading to quadratic time. Space is linear for the output.

💡 For n=20 intervals, this means up to 400 comparisons, which is inefficient for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps demonstrate understanding of the problem before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^2)`	`O(n)`	No	N/A	Mention only - never code
2. Sorting + One Pass Merge	`O(n log n)`	`O(n)`	No	N/A	Code this approach
3. In-place Merge After Sorting	`O(n log n)`	`O(1) additional`	No	N/A	Code if asked for space optimization

Practice

(1/5)

1. Consider the following Python code implementing the optimal car pooling solution. What is the return value when called with trips = [[2,1,5],[3,3,7]] and capacity = 4?

def carPooling(trips, capacity):
    max_location = 0
    for _, start, end in trips:
        max_location = max(max_location, end)
    diff = [0] * (max_location + 1)
    for num, start, end in trips:
        diff[start] += num
        diff[end] -= num
    current_passengers = 0
    for i in range(max_location + 1):
        current_passengers += diff[i]
        if current_passengers > capacity:
            return false
    return true

print(carPooling([[2,1,5],[3,3,7]], 4))

easy

A. Error due to index out of range

B. true

C. false

D. true only if capacity is at least 5

5. Consider this buggy code snippet for removing covered intervals:

def remove_covered_intervals(intervals):
    intervals.sort(key=lambda x: (x[0], x[1]))  # Bug here
    count = 0
    max_end = 0
    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
    return count

What is the bug in this code?

medium

A. The condition 'if end > max_end' should be 'if end >= max_end' to include equal ends.

B. max_end is not updated correctly inside the loop.

C. Sorting by end ascending instead of descending causes coverage detection failure.

D. The nested loop for coverage check is missing, causing incorrect results.

Start learning this pattern below

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Build difference array

Step 2: Sweep through diff to track passengers

Final Answer:

Quick Check:

Solution

Step 1: Sort intervals by end coordinate

Step 2: Iterate and count arrows

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem goal

Step 2: Identify the optimal greedy strategy

Final Answer:

Quick Check:

Solution

Step 1: Understand sorting criteria

Step 2: Single pass coverage check

Final Answer:

Quick Check:

Solution

Step 1: Analyze sorting key

Step 2: Understand coverage detection logic

Final Answer:

Quick Check: