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 ```python 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** ```text 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** ```text 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** ```text 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.