Merge time intervals

Merge overlapping intervals into a minimal set of non-overlapping intervals.

intervals sorting arrays

Write a function `merge_intervals(intervals)` that takes a list of intervals. Each interval is a list `[start, end]` where `start <= end`. Intervals may be unsorted and may overlap. Merge any overlapping intervals and return the resulting list of non-overlapping intervals sorted by start time.

Define the function signature exactly as:

```python
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
```

Rules:
- Two intervals overlap if they share any time point, including touching at a boundary (e.g., `[1,3]` and `[3,5]` overlap).
- The output must be sorted by start time.
- Do not modify the input list.

Constraints

- `0 <= len(intervals) <= 10^4`
- `-10^9 <= start <= end <= 10^9`
- Each interval is a list of exactly two integers.
- Expected time complexity: O(n log n) due to sorting. Memory: O(n).

Example

>>> merge_intervals([[1,3],[2,6],[8,10],[15,18]])
[[1,6],[8,10],[15,18]]
>>> merge_intervals([[1,4],[4,5]])
[[1,5]]
>>> merge_intervals([])
[]
>>> merge_intervals([[5,5]])
[[5,5]]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort intervals by start time first.

Iterate through sorted intervals and compare the current interval's start with the last merged interval's end.

If overlapping (current.start <= last.end), extend the last interval's end if needed.

Otherwise, add the current interval to the result.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.