Bird
Raised Fist0
Interview PrepintervalsmediumFacebookAmazonGoogleMicrosoftBloomberg

Merge Intervals

Choose your preparation mode4 modes available
📋
Problem

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

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
Edge cases: Single interval → output is the same single intervalAll intervals non-overlapping → output is the same as inputAll intervals overlapping → output is one merged interval
</>
IDE
def merge(intervals: list[list[int]]) -> list[list[int]]:public int[][] merge(int[][] intervals)vector<vector<int>> merge(vector<vector<int>>& intervals)function merge(intervals)
def merge(intervals):
    # Write your solution here
    pass
class Solution {
    public int[][] merge(int[][] intervals) {
        // Write your solution here
        return new int[0][0];
    }
}
#include <vector>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    // Write your solution here
    return {};
}
function merge(intervals) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: [[1,3],[2,6],[8,10],[15,18]]No merging performed; code returns input as is.✅ Sort intervals by start and merge overlapping intervals by comparing current start with last merged end.
Wrong: [[1,6],[8,10],[15,18],[2,6]]Incorrect merging logic that appends intervals without removing merged ones.✅ When merging, update last merged interval end and do not append duplicates.
Wrong: [[1,3],[2,6],[8,10],[15,18]]Fails to merge intervals touching at boundaries due to strict < comparison.✅ Use <= comparison to merge intervals that touch at boundaries.
Wrong: [[1,4],[5,7],[6,8]]Greedy approach merges only adjacent intervals, missing transitive merges.✅ Sort intervals and merge all overlapping intervals in one pass, not just adjacent pairs.
Wrong: TLE or timeoutNested loops causing O(n^2) time complexity on large inputs.✅ Sort intervals and merge in one pass to achieve O(n log n) time complexity.
✓
Test Cases
t1_01basic
Input{"intervals":[[1,3],[2,6],[8,10],[15,18]]}
Expected[[1,6],[8,10],[15,18]]

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

t1_02basic
Input{"intervals":[[1,4],[5,6],[7,8]]}
Expected[[1,4],[5,6],[7,8]]

All intervals are non-overlapping, so output is the same as input.

t2_01edge
Input{"intervals":[]}
Expected[]

Empty input returns empty output.

t2_02edge
Input{"intervals":[[5,5]]}
Expected[[5,5]]

Single interval with same start and end returns itself.

t2_03edge
Input{"intervals":[[1,10],[2,3],[4,5],[6,7],[8,9]]}
Expected[[1,10]]

All intervals overlap within [1,10], merged into one interval.

t3_01corner
Input{"intervals":[[1,4],[2,3],[5,7],[6,8]]}
Expected[[1,4],[5,8]]

Overlapping intervals merged correctly; greedy approach that merges only adjacent intervals fails here.

t3_02corner
Input{"intervals":[[1,3],[3,5],[6,8]]}
Expected[[1,5],[6,8]]

Intervals touching at boundaries are merged correctly.

t3_03corner
Input{"intervals":[[1,2],[2,3],[3,4],[4,5]]}
Expected[[1,5]]

Multiple intervals touching consecutively merged into one.

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this"}
⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n log n) sorting and O(n) merging to complete within 2 seconds.

Practice

(1/5)
1. Consider the following Python function implementing the line sweep algorithm to count intervals containing each point. Given intervals = [[1,4],[2,5],[7,9]] and points = [2,5,8], what is the final output of the function call count_intervals_line_sweep(intervals, points)?
easy
A. [2, 1, 1]
B. [2, 1, 0]
C. [1, 2, 1]
D. [2, 2, 1]

Solution

  1. Step 1: Sort events and process starts

    Events: (1,+1), (2,+1), (2,0), (5,0), (5+1,-1), (4+1,-1), (7,+1), (8,0), (9+1,-1). Sorted order processes starts before points, points before ends.
  2. Step 2: Track active intervals and assign counts at points

    At point 2: active=2 (intervals [1,4],[2,5]), at point 5: active=1 (only [2,5] ends at 6), at point 8: active=0 (interval [7,9] ended at 10, but 8 < 10 so active=1 actually, re-check)
  3. Correction Step 2:

    At point 8: interval [7,9] is active, so active=1. So final counts: [2,1,1]
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Counting active intervals at each point matches expected output [OK]
Hint: Remember to add 1 to interval ends for event ordering [OK]
Common Mistakes:
  • Forgetting end+1 shifts interval end
  • Misordering events causing wrong active count
  • Off-by-one in active count at points
2. You are given a list of meeting time intervals represented as pairs of start and end times. You need to determine if a single person can attend all meetings without any overlaps. Which approach guarantees an optimal and efficient solution?
easy
A. Use dynamic programming to find the maximum number of non-overlapping intervals.
B. Sort intervals by start time and check for any overlap by comparing each interval's start with the previous interval's end.
C. Use a brute force nested loop to compare every pair of intervals for overlap.
D. Sort intervals by end time and greedily select intervals that finish earliest to maximize the number of meetings attended.

Solution

  1. Step 1: Understand the problem requirement

    The problem asks if a single person can attend all meetings without overlap, so we must check if any intervals overlap.
  2. Step 2: Identify the correct approach

    Sorting intervals by start time and checking if any interval starts before the previous one ends guarantees detection of overlaps efficiently.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sorting by start time and checking overlaps is the standard approach [OK]
Hint: Sort by start time and check overlaps [OK]
Common Mistakes:
  • Confusing sorting by end time with start time for overlap detection
3. Examine the following buggy code for interval intersections:
def intervalIntersection(A, B):
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] <= B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result
What is the bug in this code?
medium
A. The condition 'if A[i][1] <= B[j][0]' should use '<' instead of '<=' to correctly detect touching intervals.
B. The pointer increments inside the else block are reversed; they should increment the pointer with the larger endpoint.
C. The overlap condition should check 'start < end' instead of 'start <= end' to avoid zero-length intervals.
D. The code does not handle empty input lists, which can cause runtime errors.

Solution

  1. Step 1: Analyze overlap condition

    Using '<=' excludes intervals that touch at a point (e.g., end == start), missing valid intersections.
  2. Step 2: Correct condition

    Changing to '<' ensures intervals that share a boundary point are considered intersecting.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Inclusive endpoints require '<' not '<=' to detect touching intervals [OK]
Hint: Check boundary conditions carefully for inclusive intervals [OK]
Common Mistakes:
  • Using <= instead of <
  • Reversing pointer increments
  • Ignoring empty inputs
4. Examine the following buggy code snippet for the minimum interval problem. Which line contains the subtle bug that can cause incorrect results on some inputs?
def min_interval_binary_search(intervals, queries):
    intervals.sort(key=lambda x: x[1] - x[0] + 1)
    lengths = [end - start for start, end in intervals]
    starts = [start for start, end in intervals]
    ends = [end for start, end in intervals]

    def covers(query, length):
        idx = bisect.bisect_right(lengths, length)
        for i in range(idx):
            if starts[i] <= query <= ends[i]:
                return True
        return False

    res = []
    max_len = lengths[-1] if lengths else 0
    for q in queries:
        left, right = 1, max_len
        ans = -1
        while left <= right:
            mid = (left + right) // 2
            if covers(q, mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        res.append(ans)
    return res
medium
A. Line 15: max_len = lengths[-1] if lengths else 0
B. Line 2: intervals.sort(key=lambda x: x[1] - x[0] + 1)
C. Line 9: for i in range(idx):
D. Line 3: lengths = [end - start for start, end in intervals]

Solution

  1. Step 1: Check interval length calculation

    Line 3 calculates lengths as end - start, missing the +1 needed for inclusive intervals.
  2. Step 2: Impact of bug

    Incorrect lengths cause wrong sorting order and coverage checks, leading to wrong minimal interval lengths.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Correct interval length must be end - start + 1 [OK]
Hint: Check interval length calculation carefully [OK]
Common Mistakes:
  • Off-by-one in length calculation
  • Not sorting intervals
  • Incorrect binary search boundaries
5. What is the time complexity of the optimal solution that sorts intervals by start ascending and end descending, then scans once to count uncovered intervals?
medium
A. O(n log n) due to sorting plus O(n) scanning
B. O(n log n) due to sorting, but scanning is O(n²) in worst case
C. O(n) because scanning is linear and sorting is negligible
D. O(n²) due to nested coverage checks

Solution

  1. Step 1: Identify sorting cost

    Sorting n intervals by start and end takes O(n log n) time.
  2. Step 2: Identify scanning cost

    Single pass scanning to count uncovered intervals is O(n).
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates, scanning is linear [OK]
Hint: Sorting dominates complexity, scanning is linear [OK]
Common Mistakes:
  • Confuse scanning as nested loops O(n²)
  • Ignore sorting cost and say O(n)
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard