MediumCoding

Merge Intervals

Asked at

BlinkitDHDocquity Holdings(PBS)

Google

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

You are given an array intervals where intervals[i] = [startᵢ, endᵢ] represents the inclusive interval startᵢ ≤ x ≤ endᵢ.

Your task is to merge every pair of intervals that overlap and return all the non-overlapping intervals that completely cover the same ranges as the original array. Two intervals overlap if they share at least one common point (i.e. start₂ ≤ end₁ and start₁ ≤ end₂).

Return the merged intervals in any order.

**Input: **intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] **Explanation: **[1,3] and [2,6] overlap --> merge to [1,6].

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Because the end of [1,4] equals the start of [4,5], they are considered overlapping.

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

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

cpp

class Solution {
public:
    vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
        // Your code goes here
    }
};

java

class Solution {
    public List<List<Integer>> merge(List<List<Integer>> intervals) {
        // Your code goes here
    }
}

python

class Solution:
    def merge(self, intervals):
        # Your code goes here

javascript

class Solution {
    merge(intervals) {
        // Your code goes here
    }
}

csharp

public class Solution {
    public IList<IList<int>> Merge(IList<IList<int>> intervals) {
        // Your code goes here
    }
}

func mergeIntervals(intervals [][]int) [][]int

Solve on LeetCode →

Stuck? Show a way to structure it+

01Sort by start, then scan left to right.
02Keep the last merged interval as the active range.
03Extend it when the next start is within its end.
04Otherwise emit it and begin a new range.

Reference answer

Sort intervals by start time. Initialize the result with the first interval, then compare each next interval to the last result interval. If next.start <= last.end, they overlap, so update last.end = max(last.end, next.end); otherwise append a new range. Sorting dominates at O(n log n), and the scan is O(n). Inclusive intervals mean touching endpoints such as [1,4] and [4,5] merge. In an interview, make the invariant explicit before writing code, trace a boundary example that breaks a tempting shortcut, state what each stored value represents, and explain why every update preserves correctness. This verification step also surfaces empty-input, duplicate-value, and numeric-limit cases.

Then expect these follow-ups

How would you merge intervals arriving as a stream?
Tests: online algorithms
How do you insert one interval into an already merged list?
Tests: two-pointer scan

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question