Merge Overlapping Intervals
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
# Merge Overlapping Intervals
Implement `merge_intervals(intervals)` for a list of closed integer intervals. Each interval is `[start, end]` with `start <= end`. Return the union as non-overlapping intervals sorted by increasing start.
Two intervals overlap when they share at least one point. Because the intervals are closed, `[1, 4]` and `[4, 6]` must merge into `[1, 6]`. The input may be unsorted and may contain duplicates or intervals fully contained in other intervals. Do not mutate the caller's list.
## Constraints
- `0 <= len(intervals) <= 100000`
- `-10^9 <= start <= end <= 10^9`
- The output must be deterministic and contain no mergeable adjacent pair.
## Examples
- `[[1, 3], [2, 6], [8, 10], [15, 18]]` returns `[[1, 6], [8, 10], [15, 18]]`.
- `[[4, 6], [1, 4], [2, 3]]` returns `[[1, 6]]`.
- `[]` returns `[]`.
## Clarifications
Explain the ordering invariant your implementation relies on, why a single comparison is sufficient after that invariant is established, and the time and auxiliary-space costs.
## Hints
Look for an ordering that makes every possible merge partner local rather than requiring all-pairs comparisons.
## Extensions
- How would the rule change for half-open intervals `[start, end)`?
- How would you merge an incoming interval into an already sorted, non-overlapping list?
- What would you change if the input were too large to fit in memory?
Quick Answer: Merge an unsorted collection of closed integer intervals into a deterministic, non-overlapping union. Explain shared-endpoint behavior, duplicates, containment, empty input, immutability, complexity, and how the contract changes for half-open or streaming intervals.
Implement `merge_intervals(intervals)` for a list of closed integer intervals. Each interval is `[start, end]` with `start <= end`. Return the union as non-overlapping intervals sorted by increasing start.
Two intervals overlap when they share at least one point. Because the intervals are closed, `[1, 4]` and `[4, 6]` must merge into `[1, 6]`, while `[1, 4]` and `[5, 6]` stay separate. The input may be unsorted and may contain duplicates or intervals fully contained in other intervals. Do not mutate the caller's list.
Output semantics: return the merged intervals sorted by strictly increasing start, with no mergeable adjacent pair remaining. This makes the answer unique for every input: it is the minimal set of disjoint closed intervals whose union equals the union of the input.
Example 1:
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: [1, 3] and [2, 6] overlap, so they merge into [1, 6]; the other two intervals touch nothing.
Example 2:
Input: intervals = [[4, 6], [1, 4], [2, 3]]
Output: [[1, 6]]
Explanation: after sorting, [1, 4] shares point 4 with [4, 6] and fully contains [2, 3], so everything collapses into [1, 6].
An empty input returns an empty list.
Constraints
- 0 <= len(intervals) <= 100000
- -10^9 <= start <= end <= 10^9
- Each interval is a closed integer interval [start, end] with start <= end
- The output must be deterministic and contain no mergeable adjacent pair
Examples
Input: ([[1, 3], [2, 6], [8, 10], [15, 18]],)
Expected Output: [[1, 6], [8, 10], [15, 18]]
Input: ([[4, 6], [1, 4], [2, 3]],)
Expected Output: [[1, 6]]
Hints
- Look for an ordering that makes every possible merge partner local rather than requiring all-pairs comparisons.
- Once that ordering is established, each interval only needs to be compared with the most recently emitted merged block.
- The intervals are closed: when the next start equals the current end, the two intervals share a point and must merge.