All problems

Merge Intervals

Medium · intervals

You are given a list intervals, where each item [start, end] is a closed range of whole numbers (both ends included).

Combine every group of ranges that overlap or touch, and return the smaller list of ranges that covers exactly the same numbers. Two ranges overlap when they share at least one number, so [1, 4] and [4, 5] become [1, 5].

The input is in no particular order. Return the result sorted by start, with no two ranges overlapping.

Examples

Example 1

Input: intervals = [[1, 3], [8, 10], [2, 6], [15, 18]]

Output: [[1, 6], [8, 10], [15, 18]]

[1, 3] and [2, 6] share the numbers 2 and 3, so they fuse into [1, 6]. The others stand alone.

Example 2

Input: intervals = [[1, 4], [4, 5]]

Output: [[1, 5]]

The ranges meet at 4, so they count as overlapping.

Example 3

Input: intervals = [[3, 4], [1, 2], [5, 6]]

Output: [[1, 2], [3, 4], [5, 6]]

Nothing overlaps. 2 and 3 are different numbers, so [1, 2] and [3, 4] stay apart.

Constraints