Merge Overlapping Closed Intervals into a Sorted Disjoint List

Problem Statement

You are given an array of closed intervals intervals where intervals[i] = [start_i, end_i]. Each interval represents the inclusive range of values from start_i to end_i.

Merge all overlapping intervals and return a list of disjoint (non-overlapping) intervals that cover all the intervals in the input. The returned list must be sorted in ascending order by start point.

Overlap Definition: Two closed intervals [a, b] and [c, d] (with a <= c) overlap if and only if c <= b. If two intervals share a single endpoint (for instance, [1, 3] and [3, 5]), they are considered overlapping and must be merged into [1, 5]. Intervals that are merely adjacent discrete integers without sharing a value (for instance, [1, 2] and [3, 4]) do not overlap and must remain separate.

Function Signature

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

Constraints

• 0 <= len(intervals) <= 100_000
• intervals[i].length == 2
• -10^9 <= start_i <= end_i <= 10^9
• The input intervals may be provided in any arbitrary order.

Examples

Example 1

Input: intervals = [[1, 3], [8, 10], [2, 6], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: Intervals [1, 3] and [2, 6] overlap, merging into [1, 6]. The rest remain disjoint.

Example 2

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: Intervals share the boundary point 4, so they merge.

Example 3

Input: intervals = [[1, 2], [3, 4]]
Output: [[1, 2], [3, 4]]
Explanation: The intervals do not share any common points, so they do not merge.

Edge Cases to Consider

• Empty input ([]) or single interval ([[1, 5]]).
• Completely nested intervals, e.g., [[1, 10], [2, 5]] merges to [[1, 10]].
• Exact duplicate intervals, e.g., [[2, 3], [2, 3]] merges to [[2, 3]].
• Intervals with equal start points but different end points.