Merge Overlapping Intervals
Company: Microsoft
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
# Merge Overlapping Intervals
## Problem
You are given an unsorted list of closed integer intervals. Each interval is represented as `[start, end]`, where `start <= end`.
Return the union of the intervals as a list that is sorted by start value and contains no overlapping intervals. Because the intervals are closed, two intervals that share an endpoint overlap and must be merged.
### Function Contract
Implement `mergeIntervals(intervals)`.
- Input: a list of two-element integer lists.
- Output: a new list of merged two-element integer lists.
### Rules and Edge Cases
- The input may be empty or contain one interval.
- Intervals may be duplicated, nested inside one another, or supplied in any order.
- Do not assume that the input is already sorted.
### Examples
```text
Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
```
```text
Input: [[4, 5], [1, 4]]
Output: [[1, 5]]
```
```hint Make overlap comparisons local
Consider what ordering lets you decide whether the next interval belongs with only the most recently produced interval.
```
```hint Treat the first result carefully
An empty result and a non-overlapping next interval can be handled by the same append operation.
```
Quick Answer: Merge an unsorted list of closed integer intervals into a sorted, non-overlapping union. Handle shared endpoints, duplicates, nested intervals, and empty input with a sort-and-scan solution and clear complexity analysis.
Implement merge_intervals(intervals) for an unsorted list of closed integer intervals [start, end], where start <= end. Return a new list representing their union, sorted by start, with no overlaps. Because intervals are closed, intervals that share an endpoint must be merged.
Constraints
- 0 <= intervals.length <= 20.
- Every interval contains exactly two integer endpoints [start, end] with start <= end.
- Each endpoint is between -3,000,000,000 and 3,000,000,000, inclusive.
- Intervals are closed, so [a, b] and [b, c] overlap.
- The input list and its interval objects must not be modified.
Examples
Input: ([],)
Expected Output: []
Explanation: An empty input has an empty union.
Input: ([[1, 3]],)
Expected Output: [[1, 3]]
Explanation: A single interval is already merged.
Hints
- Sort by start so any overlap for the next interval can be decided using only the last interval already emitted.
- When the next start is at most the current merged end, keep the current start and extend only the end.