Merge Overlapping Closed Intervals
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `merge_intervals(intervals)` for closed intervals.
Return disjoint closed intervals that cover exactly the same points, sorted by start. Intervals sharing an endpoint overlap and must be merged. Do not mutate the input.
### Constraints
- `0 <= len(intervals) <= 200000`
- Each interval is `[start, end]` with `-10^9 <= start <= end <= 10^9`.
- Input may be unsorted and may contain duplicates.
### Examples
- `[[1,3], [2,6], [8,10], [15,18]]` returns `[[1,6], [8,10], [15,18]]`.
- `[[1,4], [4,5]]` returns `[[1,5]]` because the intervals are closed.
- `[]` returns `[]`.
```hint Exercise closed-boundary behavior
Use intervals that share exactly one endpoint and verify that the shared point is not split across two outputs.
```
```hint Check representation side effects
Include duplicate intervals and verify both the canonical output and the requirement that the input remain unchanged.
```
Quick Answer: Implement `merge_intervals(intervals)` for closed intervals. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given closed intervals `[start, end]`, return disjoint closed intervals covering exactly the same points, ordered by start. Intervals sharing an endpoint overlap and must be merged. The input may be unsorted or contain duplicates, and the function must not mutate it.
Constraints
- 0 <= len(intervals) <= 200000.
- Each interval is [start, end] with -10^9 <= start <= end <= 10^9.
- Intervals are closed, so intervals sharing one endpoint overlap and must merge.
- Input order is arbitrary, duplicates are allowed, and the input must not be mutated.
Examples
Input: ([],)
Expected Output: []
Explanation: Empty input returns no intervals.
Input: ([[4, 7]],)
Expected Output: [[4, 7]]
Explanation: A singleton interval is already disjoint.
Hints
- Test empty and singleton inputs, as well as intervals that share exactly one endpoint.
- Include unsorted, nested, duplicate, and zero-length intervals while checking canonical output order.
- Use negative coordinates, both numeric limits, and a long chain of endpoint contacts.