Merge Overlapping Closed Intervals into a Sorted Disjoint List
Company: Aim Intelligent Machine
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a collection of closed integer intervals, merge every group of overlapping intervals and return the resulting disjoint intervals sorted by start.
Each interval is a pair `[start, end]` with `start <= end`. Intervals are closed, so `[start, end]` includes both endpoints. The input may be in any order and may contain duplicate or nested intervals.
### Function Signature
`merge_intervals(intervals: list[list[int]]) -> list[list[int]]`
### Rules
- Two intervals overlap when they share at least one point, including a shared endpoint. For example, `[1, 3]` and `[3, 5]` share the point `3` and belong to the same group.
- Intervals that are next to each other on the integer line but share no point, such as `[1, 2]` and `[3, 4]`, do not overlap and are not merged.
- Groups form through chains: if `A` overlaps `B` and `B` overlaps `C`, then `A`, `B`, and `C` belong to the same group even when `A` and `C` share no point.
- A group becomes one merged interval running from the smallest `start` to the largest `end` among its members. An interval that overlaps nothing forms a group by itself and is returned unchanged.
### Output
Return one `[start, end]` pair per group, sorted by `start` ascending. Different groups share no point, so their starts are distinct and this order is unique.
### Constraints
- `1 <= len(intervals) <= 100000`
- Each element of `intervals` contains exactly two integers `[start, end]`.
- `-1000000000 <= start <= end <= 1000000000`; every value fits in a signed 32-bit integer.
### Examples
Input: `intervals = [[1,3],[8,10],[2,6],[15,18]]`
Output: `[[1,6],[8,10],[15,18]]`
`[1,3]` and `[2,6]` share the points from 2 to 3, so they merge into `[1,6]`. The other two intervals overlap nothing.
Input: `intervals = [[5,7],[1,5],[7,7]]`
Output: `[[1,7]]`
`[1,5]` and `[5,7]` share the point 5, and `[7,7]` shares the point 7 with `[5,7]`, so all three intervals form one group.
Input: `intervals = [[3,4],[1,2],[-1,-1],[-3,-1]]`
Output: `[[-3,-1],[1,2],[3,4]]`
`[-1,-1]` lies inside `[-3,-1]`. `[1,2]` and `[3,4]` share no point, so they remain separate.
Overview: A coding problem that asks you to merge a list of closed integer intervals, given in any order, so that every group of overlapping intervals becomes one interval, returned sorted by start. It tests careful interval reasoning, correct handling of shared endpoints versus merely adjacent integers, nested and duplicate intervals, and efficiency on inputs of up to 100,000 intervals.
Read the full Aim Intelligent Machine Software Engineer interview experience this question came from
You are given a collection of closed integer intervals. Merge every group of overlapping intervals and return the resulting disjoint intervals sorted by start.
Each interval is a pair `[start, end]` with `start <= end`. Intervals are closed, so `[start, end]` includes both endpoints. The input may be in any order and may contain duplicate or nested intervals.
Implement `merge_intervals(intervals)`, which takes a list of `[start, end]` pairs and returns a list of `[start, end]` pairs.
Rules:
- Two intervals overlap when they share at least one point, including a shared endpoint. For example, `[1, 3]` and `[3, 5]` share the point `3` and belong to the same group.
- Intervals that are next to each other on the integer line but share no point, such as `[1, 2]` and `[3, 4]`, do not overlap and are not merged.
- Groups form through chains: if `A` overlaps `B` and `B` overlaps `C`, then `A`, `B`, and `C` belong to the same group even when `A` and `C` share no point.
- A group becomes one merged interval running from the smallest `start` to the largest `end` among its members. An interval that overlaps nothing forms a group by itself and is returned unchanged.
Output: return one `[start, end]` pair per group, sorted by `start` ascending. Different groups share no point, so their starts are distinct and this order is unique.
Constraints:
- `1 <= len(intervals) <= 100000`
- Each element of `intervals` contains exactly two integers `[start, end]`.
- `-1000000000 <= start <= end <= 1000000000`; every value fits in a signed 32-bit integer. Merged endpoints are always input values, so no value exceeds 2^31-1 (Java uses `int`, C++ uses `int`).
Example 1:
Input: `intervals = [[1,3],[8,10],[2,6],[15,18]]`
Output: `[[1,6],[8,10],[15,18]]`
`[1,3]` and `[2,6]` share the points from 2 to 3, so they merge into `[1,6]`. The other two intervals overlap nothing.
Example 2:
Input: `intervals = [[5,7],[1,5],[7,7]]`
Output: `[[1,7]]`
`[1,5]` and `[5,7]` share the point 5, and `[7,7]` shares the point 7 with `[5,7]`, so all three intervals form one group.
Constraints
- 1 <= len(intervals) <= 100000
- Each element of intervals contains exactly two integers [start, end].
- -1000000000 <= start <= end <= 1000000000; every value fits in a signed 32-bit integer.
Examples
Input: ([[1, 3], [8, 10], [2, 6], [15, 18]],)
Expected Output: [[1, 6], [8, 10], [15, 18]]
Explanation: Source example 1: [1,3] and [2,6] merge; the other two stand alone.
Input: ([[5, 7], [1, 5], [7, 7]],)
Expected Output: [[1, 7]]
Explanation: Source example 2: shared endpoints 5 and 7 chain all three into one group.
Hints
- Intervals are closed: two intervals that meet at a single endpoint count as overlapping, but [1,2] and [3,4] do not.
- A group can link intervals that do not directly touch each other, so think about an order in which each interval only needs to be compared with the group built so far.
- When an interval joins a group, the group's end should never get smaller; watch for intervals nested inside a longer one.