Merge overlapping intervals

Problem Statement

Given an array of intervals where each interval is defined as [start, end], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Function Signature

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

Constraints

• 1 <= intervals.length <= 10^4
• 0 <= start_i <= end_i <= 10^4

Examples

Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since [1,3] and [2,6] overlap, merge them into [1,6].

Example 2: Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals that share a boundary point are considered overlapping.

Edge Cases

• Empty input list.
• A single interval.
• Intervals fully contained within another interval (e.g., [[1,10], [2,5]]).
• Intervals already sorted or in reverse order.