Quick Overview

An interval-merging coding question: given closed integer intervals in any order, merge every group that overlaps or touches at a shared endpoint and return the disjoint result sorted by start. It tests careful reasoning about nested, repeated and touching intervals and producing an efficient, exactly ordered result.

Merge Overlapping Closed Integer Intervals into a Sorted Disjoint List

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Given a list of closed integer intervals, merge every group of intervals that overlap and return the resulting disjoint intervals sorted by their start. The candidate's report names this online-assessment question only as interval merging; this version fixes the exact rules below. ### Function Signature ```python def merge_intervals(intervals: list[list[int]]) -> list[list[int]]: ``` ### Rules - Each interval is a pair `[start, end]` with `start <= end`. It covers every point from `start` to `end`, both ends included. - Two intervals overlap when they share at least one point. Intervals that only touch at an endpoint, such as `[1, 4]` and `[4, 6]`, share the point 4 and are merged into `[1, 6]`. Intervals such as `[1, 4]` and `[5, 6]` share no point and stay separate. - Merging is transitive: if A overlaps B and B overlaps C, all three become one interval even when A and C do not overlap each other. - The input may be in any order and may contain repeated intervals and intervals nested inside others. - Each returned interval is `[start, end]`, where `start` is the smallest start and `end` the largest end in its merged group. No two returned intervals share a point. - Return the merged intervals sorted by `start` ascending. An empty input returns `[]`. ### Constraints - `0 <= len(intervals) <= 10^5` - `-10^9 <= start <= end <= 10^9` for every interval ### Examples **Example 1** ```text Input: intervals = [[5, 7], [1, 3], [2, 4], [9, 9]] Output: [[1, 4], [5, 7], [9, 9]] ``` `[1, 3]` and `[2, 4]` share the points 2 to 3 and merge into `[1, 4]`. `[5, 7]` starts after 4, so it stays separate, and the single-point interval `[9, 9]` overlaps nothing. **Example 2** ```text Input: intervals = [[1, 4], [4, 6], [6, 6], [0, 0]] Output: [[0, 0], [1, 6]] ``` `[1, 4]` and `[4, 6]` share the point 4, and `[6, 6]` shares the point 6, so all three merge into `[1, 6]`. `[0, 0]` shares no point with them. **Example 3** ```text Input: intervals = [[2, 3], [1, 10], [11, 12], [4, 8]] Output: [[1, 10], [11, 12]] ``` `[2, 3]` and `[4, 8]` lie inside `[1, 10]`. `[11, 12]` starts after 10 and shares no point with it.

Overview: An interval-merging coding question: given closed integer intervals in any order, merge every group that overlaps or touches at a shared endpoint and return the disjoint result sorted by start. It tests careful reasoning about nested, repeated and touching intervals and producing an efficient, exactly ordered result.

You are given a list of closed integer intervals. Each interval is a pair `[start, end]` with `start <= end`, and it covers every point from `start` to `end`, both ends included. Two intervals **overlap** when they share at least one point. Intervals that only touch at an endpoint, such as `[1, 4]` and `[4, 6]`, share the point 4 and are merged into `[1, 6]`. Intervals such as `[1, 4]` and `[5, 6]` share no point and stay separate. Merging is transitive: if A overlaps B and B overlaps C, all three become one interval even when A and C do not overlap each other. The input may be in any order and may contain repeated intervals and intervals nested inside others. Implement `merge_intervals(intervals)`, which merges every group of overlapping intervals and returns the resulting disjoint intervals: - Each returned interval is `[start, end]`, where `start` is the smallest start and `end` is the largest end in its merged group. No two returned intervals share a point. - Return the merged intervals sorted by `start` ascending. - An empty input returns `[]`. ### Example 1 ```text Input: intervals = [[5, 7], [1, 3], [2, 4], [9, 9]] Output: [[1, 4], [5, 7], [9, 9]] ``` `[1, 3]` and `[2, 4]` share the points 2 to 3 and merge into `[1, 4]`. `[5, 7]` starts after 4, so it stays separate, and the single-point interval `[9, 9]` overlaps nothing. ### Example 2 ```text Input: intervals = [[1, 4], [4, 6], [6, 6], [0, 0]] Output: [[0, 0], [1, 6]] ``` `[1, 4]` and `[4, 6]` share the point 4, and `[6, 6]` shares the point 6, so all three merge into `[1, 6]`. `[0, 0]` shares no point with them. ### Constraints - `0 <= len(intervals) <= 10^5` - `-10^9 <= start <= end <= 10^9` for every interval - Every input and output value lies within the signed 32-bit range (no value exceeds 2^31 - 1 in absolute value), so Java uses `int[][]` and C++ uses `std::vector<std::vector<int>>`.

Constraints

  • 0 <= len(intervals) <= 10^5
  • -10^9 <= start <= end <= 10^9 for every interval
  • Every input and output value lies within the signed 32-bit range (no value exceeds 2^31 - 1 in absolute value)

Examples

Input: ([],)

Expected Output: []

Explanation: Empty input returns an empty list.

Input: ([[3, 8]],)

Expected Output: [[3, 8]]

Explanation: A single interval is returned unchanged.

Hints

  1. Intervals that only touch at one endpoint, such as [1, 4] and [4, 6], share that point and belong in the same merged interval.
  2. A merged interval ends at the largest end among all of its members, which is not necessarily the end of the member you looked at last: an interval can sit entirely inside another.
  3. The input may arrive in any order and merging is transitive, so a group can keep growing through a chain of intervals; make sure no remaining interval can still join a group before you report it.

Merge Overlapping Closed Intervals

easyAmazonSoftware Engineer

You are given a list of closed integer intervals. Each interval is a pair [start, end] with start <= end, and it covers every point from start to end, both ends included.

Two intervals overlap when they share at least one point. Intervals that only touch at an endpoint, such as [1, 4] and [4, 6], share the point 4 and are merged into [1, 6]. Intervals such as [1, 4] and [5, 6] share no point and stay separate. Merging is transitive: if A overlaps B and B overlaps C, all three become one interval even when A and C do not overlap each other.

The input may be in any order and may contain repeated intervals and intervals nested inside others.

Implement merge_intervals(intervals), which merges every group of overlapping intervals and returns the resulting disjoint intervals:

  • Each returned interval is [start, end], where start is the smallest start and end is the largest end in its merged group. No two returned intervals share a point.
  • Return the merged intervals sorted by start ascending.
  • An empty input returns [].

Example 1

Input:  intervals = [[5, 7], [1, 3], [2, 4], [9, 9]]
Output: [[1, 4], [5, 7], [9, 9]]

[1, 3] and [2, 4] share the points 2 to 3 and merge into [1, 4]. [5, 7] starts after 4, so it stays separate, and the single-point interval [9, 9] overlaps nothing.

Example 2

Input:  intervals = [[1, 4], [4, 6], [6, 6], [0, 0]]
Output: [[0, 0], [1, 6]]

[1, 4] and [4, 6] share the point 4, and [6, 6] shares the point 6, so all three merge into [1, 6]. [0, 0] shares no point with them.

Constraints

  • 0 <= len(intervals) <= 10^5
  • -10^9 <= start <= end <= 10^9 for every interval
  • Every input and output value lies within the signed 32-bit range (no value exceeds 2^31 - 1 in absolute value), so Java uses int[][] and C++ uses std::vector<std::vector<int>>.

Examples

Example 1
Input
([],)
Output
[]
Notes
Empty input returns an empty list.
Example 2
Input
([[3, 8]],)
Output
[[3, 8]]
Notes
A single interval is returned unchanged.

Constraints

  • •0 <= len(intervals) <= 10^5
  • •-10^9 <= start <= end <= 10^9 for every interval
  • •Every input and output value lies within the signed 32-bit range (no value exceeds 2^31 - 1 in absolute value)

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
Sample call
merge_intervals([])
Language
Case 1
Input
([],)
Expected
[]
Case 2
Input
([[3, 8]],)
Expected
[[3, 8]]

Browse More Questions

Show the approach

Approach

Sort a copy of the intervals by start (ties broken by end), then sweep once while holding the current merged group as [cur_start, cur_end]. For the next interval [start, end]: if start <= cur_end, the point start lies inside the contiguous range the group already covers (the union of a merged group of closed intervals is one unbroken range), so the interval shares a point with a group member and joins the group; cur_end becomes max(cur_end, end). Taking the maximum matters because a nested interval can end before the group does. Otherwise start > cur_end, and since every later interval starts at or after start, nothing later can share a point with the group, so the group is closed and emitted as [cur_start, cur_end]; cur_start is the group's smallest start because the intervals were visited in start order. The test is <= rather than < because closed intervals that only touch at an endpoint share that point and must merge. Invariant: after the first i sorted intervals, the emitted groups plus the open group are exactly the merged groups of those i intervals, in increasing start order and separated by gaps, so the final output is disjoint and sorted by start. Edge cases: an empty input returns []; a single interval, including a single point [x, x], returns itself; repeated intervals collapse into one; coordinates at -10^9 and 10^9 are compared directly, and the Java comparator uses Integer.compare instead of subtraction so it cannot overflow 32-bit.

Time complexity:
O(n log n)
Space complexity:
O(n)