Solution: Merge Intervals

Statement

We are given an array of closed intervalsclosedintervals called intervals, where each interval has a start time and an end time and is represented as intervals[i] = [starti, endi]. Your task is to merge the overlapping intervalsOverlapping intervals are two or more intervals with at least one common point in time. and return a new output array consisting of only the non-overlapping intervals.

Constraints:

• $1 \leq$ intervals.length $\leq10^3$

• intervals[i].length $== 2$

• $0\leq$ starti $\leq$ endi $\leq10^4$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow, based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach to merging intervals involves comparing each interval with all the intervals that come after it. If two intervals overlap, they are merged into a single interval by updating the start to the minimum of both start times and the end to the maximum of both end times. After merging, the second interval (the one being compared) is removed from the list, as its range is now included in the updated interval. The algorithm then checks for further overlaps with the updated interval from the same position. This process repeats until all overlapping intervals have been merged, resulting in a final list of non-overlapping intervals.

This process continues until all overlapping intervals are merged. While this method is easy to understand and doesn’t require extra space, it can be inefficient for large inputs because it compares each interval with many others, leading to a time complexity of $O(n^2)$.

Optimized approach using the merge intervals pattern

The optimized approach starts by sorting the intervals in ascending order based on their start times. This step ensures overlapping intervals are positioned next to each other, making identifying and merging them easier. Once sorted, the algorithm initializes a result list with the first interval. It then iterates through the remaining intervals one by one, comparing each to the last interval in the result list.

If the current interval overlaps with the last one in the result (i.e., its start time is less than or equal to the end time of the last interval), the two intervals are merged by updating the end time to the maximum of both intervals’ end times. If there is no overlap, the current interval is added to the result list as a new entry. This process continues until all intervals have been processed. In the end, the result list contains the merged, non-overlapping intervals.

Step-by-step solution construction

The first step is to sort the list of intervals based on their start times. This ensures that we are processing the intervals in the correct order, from the earliest start time to the latest, to easily detect overlapping intervals as we move through the list.

After sorting, we initialize a result list and add the first interval from the sorted list to it. This result list will eventually contain all the merged intervals.

The code below implements the steps above: