Combine Overlapping Closed Intervals Into a Sorted Disjoint List

You are given a list of closed intervals with integer endpoints, in no particular order. Combine every group of overlapping intervals into a single interval, and return the resulting intervals sorted by their start.

Function Signature

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:

Rules

• Each interval is [start, end] with start <= end, and it includes both endpoints.
• Two intervals overlap when they share at least one point. Intervals that only touch at an endpoint, such as [1, 4] and [4, 5], overlap and must be combined. Intervals separated by a gap, such as [1, 2] and [3, 4], do not overlap, even though no integer lies strictly between them.
• Overlap chains: if A overlaps B and B overlaps C, then A, B and C all end up in one interval, even when A and C do not overlap each other.
• Each returned interval is [smallest start, largest end] over the input intervals in its group, so the returned intervals cover exactly the same points as the input.
• The input may contain duplicates and intervals nested inside others.
• Return the combined intervals in ascending order of start. No two returned intervals overlap, so this order is unique.

Constraints

• 1 <= len(intervals) <= 10^5
• Every interval has exactly two integers, and -10^9 <= start <= end <= 10^9.

Examples

Example 1

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

[2, 3] lies inside [1, 4]. [5, 7] and [6, 9] overlap and combine into [5, 9]. [1, 4] and [5, 9] share no point.

Example 2

Input: intervals = [[3, 4], [1, 2], [4, 4]]
Output: [[1, 2], [3, 4]]

[3, 4] and [4, 4] share the point 4, so they combine into [3, 4]. [1, 2] and [3, 4] share no point, so they stay separate.

Example 3

Input: intervals = [[-5, -1], [-3, 2], [-5, -1]]
Output: [[-5, 2]]

The duplicate [-5, -1] and the overlapping [-3, 2] all combine into one interval.