Merge Overlapping Closed Intervals Into a Sorted Disjoint List

Given a list of closed integer intervals, merge every group of overlapping intervals and return the resulting disjoint intervals.

Function Signature

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

Each interval is [start, end] with start <= end, and it contains every point from start to end, inclusive.

Rules

• The input may be in any order, and it may contain duplicate intervals and intervals nested inside others.
• Two intervals overlap when they share at least one point. Intervals that only touch, such as [1, 3] and [3, 5], share the point 3 and must be merged into [1, 5]. The intervals [1, 2] and [3, 4] share no point and stay separate.
• Merging is transitive: if A overlaps B and B overlaps C, all three become one interval, even when A and C do not overlap.
• Return the merged intervals sorted by start in ascending order. No two returned intervals share a point, and together they cover exactly the points covered by the input.

Constraints

• 1 <= len(intervals) <= 10^5
• -10^9 <= start <= end <= 10^9

Examples

Example 1

Input: intervals = [[8, 10], [1, 4], [3, 6], [12, 12]]
Output: [[1, 6], [8, 10], [12, 12]]

[1, 4] and [3, 6] overlap on 3 to 4 and become [1, 6]. [8, 10] and the single point [12, 12] overlap nothing.

Example 2

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

[1, 3] and [3, 5] touch at 3, so they merge. [1, 5] and [6, 7] share no point.

Example 3

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

[3, 4] and [5, 5] lie inside [2, 9], and [1, 2] touches it at 2.