Merge overlapping intervals
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of closed intervals on the number line, where each interval is represented as a pair of integers `[start, end]` with `start <= end`.
Write a function that merges all overlapping intervals and returns a new list of non-overlapping intervals that cover exactly the same ranges as the input.
The output list can be returned in any order, but within each interval the first element must be the start and the second element must be the end.
**Example:**
- Input: `[[1,3], [2,6], [8,10], [15,18]]`
- Output: `[[1,6], [8,10], [15,18]]`
- Explanation: Intervals `[1,3]` and `[2,6]` overlap and are merged into `[1,6]`. The other intervals do not overlap with any others.
**Another example:**
- Input: `[[1,4], [4,5]]`
- Output: `[[1,5]]`
**Constraints:**
- `1 <= n <= 10^5` where `n` is the number of intervals
- Interval endpoints are integers in the range `[-10^9, 10^9]`
Quick Answer: This question evaluates understanding of interval operations, array manipulation, and algorithmic efficiency, along with correct handling of edge cases and large-scale inputs.
Merge a list of closed intervals into sorted, non-overlapping intervals covering the same ranges.
Constraints
- Intervals are [start, end] pairs with start <= end.
- Closed intervals that touch at an endpoint are considered overlapping.
- Return intervals sorted by start for deterministic grading.
Examples
Input: ([[1,3],[2,6],[8,10],[15,18]],)
Expected Output: [[1, 6], [8, 10], [15, 18]]
Explanation: The first two intervals overlap and merge.
Input: ([[1,4],[4,5]],)
Expected Output: [[1, 5]]
Explanation: Closed intervals that touch are merged.
Input: ([[5,7],[1,2],[2,3],[10,10]],)
Expected Output: [[1, 3], [5, 7], [10, 10]]
Explanation: Input order does not matter.
Input: ([],)
Expected Output: []
Explanation: An empty interval list returns empty output.
Hints
- Sort by start first.
- Extend the previous merged interval whenever the next interval overlaps or touches it.