Merge Overlapping Time Ranges
Company: Amazon
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Merge Overlapping Time Ranges
You are building the scheduling backend for a shared conference room. Each reservation that has ever been placed is recorded as a pair `[start, end]` of integer timestamps (epoch seconds), where `start <= end`. The reservations are stored in arbitrary order and many of them overlap, because the same block of time was booked, re-booked, and extended by different people.
Two reservations should be combined when they overlap **or touch at an endpoint**. For example, `[10, 30]` and `[30, 45]` combine into `[10, 45]`, and `[10, 30]` and `[20, 25]` combine into `[10, 30]`.
Write a function that takes the list of reservations and returns the **smallest possible** list of non-overlapping reservations that covers exactly the same set of seconds. The returned intervals must be sorted in ascending order by start time, and no two of them may overlap or touch.
## Input
- `intervals`: a list of `[start, end]` integer pairs.
- `0 <= start <= end <= 10^9`
- The list may be empty.
- `0 <= len(intervals) <= 10^5`
## Output
- A list of merged `[start, end]` pairs, sorted ascending by `start`, in which no two intervals overlap or touch. For an empty input, return an empty list.
## Examples
**Example 1**
```
Input: [[10, 30], [20, 25], [40, 50], [30, 35]]
Output: [[10, 35], [40, 50]]
```
Explanation: `[10, 30]`, `[20, 25]`, and `[30, 35]` overlap or touch one another and collapse into `[10, 35]`. `[40, 50]` does not touch `[10, 35]` (because `35 < 40`), so it stays on its own.
**Example 2**
```
Input: [[5, 8], [1, 4]]
Output: [[1, 4], [5, 8]]
```
Explanation: The two reservations do not overlap or touch (`4 < 5`), so they are simply returned sorted by start time.
**Example 3**
```
Input: []
Output: []
```
## Notes
- Intervals are inclusive on both ends; `[a, b]` covers every second `t` with `a <= t <= b`.
- Treat intervals that share only a single endpoint (e.g. `[1, 4]` and `[4, 9]`) as touching, so they merge into `[1, 9]`.
Quick Answer: This question evaluates a candidate's ability to work with interval merging, a core array and sorting problem in technical interviews. It tests understanding of sorting-based algorithms and edge-case handling around overlapping or touching ranges, assessing practical coding proficiency rather than pure theory. This type of problem is a staple of coding interview rounds for engineering roles.
You are building the scheduling backend for a shared conference room. Each reservation is recorded as a pair `[start, end]` of integer timestamps (epoch seconds), where `start <= end`. Reservations are stored in arbitrary order and many overlap.
Two reservations should be combined when they **overlap OR touch at an endpoint**. For example, `[10, 30]` and `[30, 45]` combine into `[10, 45]`, and `[10, 30]` and `[20, 25]` combine into `[10, 30]`.
Write a function `merge_intervals(intervals)` that returns the **smallest possible** list of non-overlapping reservations covering exactly the same set of seconds. The result must be sorted ascending by start time, and no two returned intervals may overlap or touch.
### Input
- `intervals`: a list of `[start, end]` integer pairs.
- `0 <= start <= end <= 10^9`
- `0 <= len(intervals) <= 10^5`
- The list may be empty.
### Output
- A list of merged `[start, end]` pairs, sorted ascending by `start`, in which no two intervals overlap or touch. For an empty input, return an empty list.
### Notes
- Intervals are inclusive on both ends: `[a, b]` covers every second `t` with `a <= t <= b`.
- Intervals that share only a single endpoint (e.g. `[1, 4]` and `[4, 9]`) count as touching and merge into `[1, 9]`.
Constraints
- 0 <= start <= end <= 10^9
- 0 <= len(intervals) <= 10^5
- Intervals are inclusive on both ends
- Intervals that only touch at an endpoint must be merged
Examples
Input: ([[10, 30], [20, 25], [40, 50], [30, 35]],)
Expected Output: [[10, 35], [40, 50]]
Explanation: [10,30], [20,25], [30,35] overlap or touch and collapse into [10,35]; [40,50] stays separate since 35 < 40.
Input: ([[5, 8], [1, 4]],)
Expected Output: [[1, 4], [5, 8]]
Explanation: The two reservations neither overlap nor touch (4 < 5), so they are returned sorted by start.
Input: ([],)
Expected Output: []
Explanation: Empty input yields an empty list.
Input: ([[1, 4], [4, 9]],)
Expected Output: [[1, 9]]
Explanation: They share only the endpoint 4, which counts as touching, so they merge into [1,9].
Input: ([[7, 7]],)
Expected Output: [[7, 7]]
Explanation: A single zero-length interval is returned unchanged.
Input: ([[1, 10], [2, 3], [4, 5], [6, 7]],)
Expected Output: [[1, 10]]
Explanation: Every later interval is fully contained in [1,10], so all collapse into it.
Input: ([[5, 5], [5, 5], [5, 5]],)
Expected Output: [[5, 5]]
Explanation: Exact duplicates all merge into a single interval.
Input: ([[0, 1000000000], [500, 600]],)
Expected Output: [[0, 1000000000]]
Explanation: The small interval is contained within the large one across the full timestamp range.
Input: ([[3, 4], [1, 2]],)
Expected Output: [[1, 2], [3, 4]]
Explanation: Unsorted input; 2 < 3 means no touch, so both remain, sorted by start.
Input: ([[1, 2], [2, 2], [2, 3]],)
Expected Output: [[1, 3]]
Explanation: Chained touching at the point 2 merges all three into [1,3].
Hints
- Sort the intervals by their start value first. Once sorted, a single left-to-right pass is enough.
- Keep a running 'current' interval. Extend it whenever the next interval's start is <= the current end (use <=, not <, so touching intervals merge).
- When the next interval's start is strictly greater than the current end, close off the current interval and start a new one.