6. Merge Intervals

Medium · Array

Given an array of intervals where each interval is represented as [start, end], merge all overlapping intervals and return an array of the merged intervals.

Two intervals [a, b] and [c, d] overlap if they share any point, including endpoints. For example, [1, 3] and [3, 5] overlap and should merge into [1, 5].

Return the merged intervals in sorted order by their start time.

Examples

Example 1
Input: [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: Intervals [1, 3] and [2, 6] overlap, so they merge into [1, 6]. The other intervals do not overlap with any others.
Example 2
Input: [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: Intervals [1, 4] and [4, 5] share the endpoint 4, so they overlap and merge into [1, 5].

Constraints