Merge Overlapping Intervals [Solution]

This exercise evaluates your understanding of interval manipulation and sorting, as well as your ability to handle and merge overlapping intervals efficiently.

Below is a Python implementation of the merge_intervals function to merge overlapping intervals:

from typing import List

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

    # Sort intervals based on the start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for interval in intervals[1:]:
        current_start, current_end = merged[-1]
        next_start, next_end = interval

        # Check for overlap
        if current_end >= next_start:
            # Merge overlapping intervals
            merged[-1] = [current_start, max(current_end, next_end)]
        else:
            # No overlap, add the interval to the merged list
            merged.append(interval)

    return merged

# Example usage:
input_intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
result = merge_intervals(input_intervals)
print(result)

Time Complexity:

This solution sorts the intervals based on their start times and then iterates through the sorted list to merge overlapping intervals. The time complexity is O(n log n) due to the sorting step.

Space Complexity:

The space complexity is O(1) since the merged list is modified in place.