Merge Overlapping Intervals

Merge Overlapping Intervals

You are given an array of intervals where each interval is defined as [start, end]. Write a function merge_intervals(intervals) that merges all overlapping intervals and returns an array of the non-overlapping intervals that cover all the intervals in the input.

Two intervals [a, b] and [c, d] overlap if there is any point that lies in both intervals (e.g., [1, 3] and [2, 4] overlap).

Function Signature

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

Constraints

• 1 <= intervals.length <= 10^4
• 0 <= start <= end <= 10^4

Examples

Example 1: Input: intervals = [[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: intervals = [[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 (e.g., [[1, 10], [2, 5]]).
• Intervals already sorted or completely unsorted.