Merge Overlapping Intervals with a Sweep
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
# Merge Overlapping Intervals with a Sweep
Implement `merge_intervals(intervals)` for closed integer intervals `[start, end]` with `start <= end`. Return their union as non-overlapping intervals sorted by start. Intervals sharing an endpoint merge.
Constraints: up to `200000` intervals; every endpoint is an integer in `[-10^9, 10^9]`. Return an array of two-integer arrays. Do not mutate the input. Aim for `O(n log n)` time.
```hint Focus on boundary policy
Test nested intervals, disjoint intervals, duplicate intervals, and two intervals that share one endpoint.
```
Quick Answer: Implement `merge_intervals(intervals)` for closed integer intervals `[start, end]` with `start <= end`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given closed integer intervals `[start, end]` with `start <= end`, return their union as non-overlapping intervals ordered by ascending start. Because the intervals are closed, intervals sharing an endpoint merge. Do not mutate the input.
Constraints
- 0 <= len(intervals) <= 200000; each interval has exactly two integers start <= end.
- Every endpoint is from -10^9 through 10^9.
- Intervals are closed, so a shared endpoint belongs to both and must merge; the input must not be mutated.
Examples
Input: ([],)
Expected Output: []
Explanation: An empty input has an empty union.
Input: ([[2, 2]],)
Expected Output: [[2, 2]]
Explanation: A singleton point interval remains unchanged.
Hints
- Test empty and singleton inputs, duplicates, nested intervals, and disjoint intervals.
- Include two closed intervals sharing exactly one endpoint.
- Use unordered intervals spanning negative and positive endpoint values, then verify canonical output order.