Microsoft · Coding 1 of 3

Merge Intervals

Merge every group of overlapping intervals.

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

Practice question: an editorial practice prompt, not a claim that Microsoft asks this exact question. Interviews vary by role, level, team, and location.

Problem

Problem statement

Given an array intervals where intervals[i] = [start, end], merge every group of overlapping intervals and return the resulting non-overlapping intervals, sorted by start.

In this version, intervals that only touch — such as [1, 4] and [4, 5] — count as overlapping. Confirm that rule with your interviewer before you code.

Examples

Example 1
Input
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output
[[1, 6], [8, 10], [15, 18]]

Why: [1, 3] and [2, 6] overlap, so they become [1, 6].

Example 2
Input
intervals = [[1, 4], [4, 5]]
Output
[[1, 5]]

Why: Touching intervals merge.

Example 3
Input
intervals = [[1, 10], [2, 3], [4, 5]]
Output
[[1, 10]]

Why: Nested intervals are absorbed.

Constraints

  • 1 ≤ intervals.length ≤ 10⁴
  • 0 ≤ start ≤ end ≤ 10⁴
  • The input is not necessarily sorted.
In the interview

How to answer it out loud

What it tests: Sorting, boundary reasoning, and the ability to explain complexity.

  1. 1
    Clarify

    Clarify whether touching intervals merge.

  2. 2
    Implement

    Sort by start time and maintain one current interval.

  3. 3
    Verify

    Test nested, disjoint, empty, and touching cases.

Approaches

From brute force to the best solution

ApproachIdeaTimeSpace
Pairwise mergingRepeatedly merge any two overlapping intervals until no pair overlaps.O(n²) or worseO(n)
Sort, then sweepBestSort by start; extend the last merged interval or start a new one.O(n log n)O(n)
Key insight

After sorting by start, an interval can only overlap the most recently merged one — so a single left-to-right pass decides every merge.

Solution

Reference solution

Each version is self-contained and has been run against the examples and test cases on this page.

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:    merged = []    for start, end in sorted(intervals, key=lambda iv: iv[0]):        if merged and start <= merged[-1][1]:     # overlaps (or touches) the last one            merged[-1][1] = max(merged[-1][1], end)        else:            merged.append([start, end])    return merged
Time
O(n log n)
Space
O(n)
Approach
Sort, then sweep
Test cases

Edge cases to run before you say “done”

InputExpectedWhy it matters
[[8, 10], [1, 3], [2, 6]][[1, 6], [8, 10]]Unsorted input.
[[1, 10], [2, 3]][[1, 10]]A nested interval must not shrink the end to 3.
[[5, 5]][[5, 5]]A single zero-length interval.
Likely follow-ups

Answer the main question first, then take these on one at a time:

  • Can it be done without sorting?
  • What if input is streamed?
  • How would you preserve labels?
Avoid these mistakes

Check your recording or written solution against this list:

  • Missing the touching-boundary rule
  • Mutating unexpectedly
  • No complexity analysis
Sources and methodology

This guide combines general interview-practice patterns with the public hiring material below. The practice prompt and coaching are PiriPiri AI editorial content, not official Microsoft questions or answers.

Microsoft Careers: technical interviewing ↗
Official sources reviewed 20 September 2026.