Interval Merging
You are given a list of $n$ intervals, where each interval is $[x_i, y_i]$ with $x_i \leq y_i$. The intervals may be unsorted and may overlap.
Return the merged list of disjoint intervals in increasing order of start point.
**Constraints:**
-
\leq n \leq 10^5$
- Coordinates are integers in $[-10^9, 10^9]$
- Achieve $O(n \log n)$ time and $O(1)$ extra space beyond the output (in-place sort is allowed)
**Examples:**
Input: $[[1,3],[2,6],[8,10],[15,18]]$ -- Output: $[[1,6],[8,10],[15,18]]$
(Intervals $[1,3]$ and $[2,6]$ overlap, merged to $[1,6]$)
Input: $[[1,4],[4,5]]$ -- Output: $[[1,5]]$
($[1,4]$ and $[4,5]$ share endpoint 4, merged to $[1,5]$)
Input: $[[1,4],[2,3]]$ -- Output: $[[1,4]]$
($[2,3]$ is entirely contained within $[1,4]$)
Also discuss: how does the answer change if intervals are open ($(x_i, y_i)$) vs. closed ($[x_i, y_i]$)?
Open the full interactive solver, hints, and worked solution →