data_structures.arrays.merge_intervals

Functions

merge_intervals(→ list[list[int]])

Merge all overlapping intervals.

Module Contents

data_structures.arrays.merge_intervals.merge_intervals(intervals: list[list[int]]) → list[list[int]]

Merge all overlapping intervals.

Each interval is represented as a list of two integers [start, end]. The function merges overlapping intervals and returns a list of non-overlapping intervals sorted by start time.

Parameters: intervals (list[list[int]]): A list of intervals.

Returns: list[list[int]]: A list of merged non-overlapping intervals.

Edge Cases Handled: - Empty list: returns [] - Single interval: returns the interval itself - Intervals already sorted or unsorted - Fully overlapping intervals - Invalid intervals (e.g., [[]] or intervals not having exactly

2 integers) raise ValueError

Examples: >>> merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]) [[1, 6], [8, 10], [15, 18]] >>> merge_intervals([[1, 4], [4, 5]]) [[1, 5]] >>> merge_intervals([[6, 8], [1, 3], [2, 4]]) [[1, 4], [6, 8]] >>> merge_intervals([]) [] >>> merge_intervals([[1, 4]]) [[1, 4]]

Time Complexity: O(n log n) - sorting the intervals, where n is the number of intervals.

Space Complexity: O(n) - storing the merged intervals.