Merge Intervals

Problem Description

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Key Insights

• Overlapping intervals can be merged into a single interval that spans the start of the first interval to the end of the last overlapping interval.
• Sorting the intervals by their start times simplifies the merging process.
• By iterating through the sorted intervals, we can determine if the current interval overlaps with the last added interval in the result list.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step, where n is the number of intervals.
Space Complexity: O(n) for storing the merged intervals in the result list.

Solution

To solve the problem, we will:

1. Sort the intervals based on the starting time.
2. Initialize a result list to hold the merged intervals.
3. Iterate through the sorted intervals and compare each interval with the last interval in the result list:
   • If they overlap, merge them by updating the end of the last interval in the result list.
   • If they do not overlap, add the current interval to the result list.

The algorithm primarily uses a list to store intervals and sorting as the main approach to facilitate the merging process.

Code Solutions