Merge Overlapping Intervals

Problem Statement

You are given an array of closed integer intervals, intervals, where intervals[i] = [start_i, end_i]. The input list is unsorted, and intervals may overlap, contain one another, or be identical.

Two intervals [a, b] and [c, d] overlap if they share at least one common point. Note that intervals touching at a single boundary (for example, [1, 3] and [3, 5]) are considered overlapping and should be merged into a single interval ([1, 5]).

Write a function that merges all overlapping intervals and returns an array of non-overlapping intervals that cover all the points in the input. The output list must be sorted in ascending order by their start points.

Function Signature

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

Constraints

• 0 <= len(intervals) <= 10^5
• intervals[i].length == 2
• -10^9 <= start_i <= end_i <= 10^9

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, so they merge into [1, 6]. The remaining intervals do not overlap.

Example 2

Input: intervals = [[4, 7], [1, 4], [-2, 0]]
Output: [[-2, 0], [1, 7]]
Explanation:
Intervals [1, 4] and [4, 7] touch at point 4, so they merge into [1, 7].

Edge Cases to Consider

• Empty input list [] should return [].
• Single interval inputs should return unchanged.
• Completely nested intervals (e.g., [[1, 10], [2, 5]] merges to [[1, 10]]).
• Negative and zero coordinates.
• Duplicate identical intervals.