Merge Intervals Explained: From Brute Force to an Optimal O(n log n) Solution

Merge Intervals is a common technique used in everyday scenarios such as scheduling meetings, booking rooms, and managing time ranges. An interval is simply a range with a start and an end point. For example,[2, 5] represents the range from 2 to 5.Using this technique, overlapping or adjacent intervals are combined into a single interval, which helps optimize schedules and resource allocation. In programming, the Merge Intervals algorithm is widely used in calendar applications, resource management systems, and even genome analysis. It is also one of the most frequently asked topics in technical interviews at companies such as Google, Meta,Amazon.In this article, we will learn what the Merge Intervals problem is and how to solve it efficiently.

As a classic example, let us consider Merge Intervals (LeetCode 56).

We are given an array called intervals, where each element is in the form [start,end] and represents an interval. Our task is to merge all overlapping intervals and return an array of non-overlapping intervals.

Example 1

Input:intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation:The intervals [1,3]and [2,6] overlap because 2≤3, so they are merged into [1,6].

In general, two intervals [a,b] and [c,d](where a≤b , c≤d, and we assume a≤c, meaning the first interval starts earlier) overlap if c≤b.

The first solution that usually comes to mind is to compare every interval with every other interval.

def merge(intervals):
     if not intervals:
            return []
        result = [interval[:] for interval in intervals]
        merged = True
        while merged:
            merged = False
            i = 0
            while i < len(result):
                j = i + 1
                while j < len(result):
                    a, b = result[i]
                    c, d = result[j]
                    if a <= d and c <= b:
                        result[i] = [min(a, c), max(b, d)]
                        result.pop(j)
                        merged = True
                    else:
                        j += 1
                i += 1
        return result

At first glance, the brute force approach seems simple, but it has an important drawback: after two intervals are merged, the newly created interval may overlap with intervals that were checked earlier. Because of this, an outer loop is required to repeat the process until no more merges are possible.

This additional complexity clearly demonstrates why the sorted approach is superior.

Now, let’s look at the optimal solution.

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)
    return merged

I tested both solutions on the same 172 test cases, and the results are shown in the screenshots. The second solution was approximately 975 times faster.

The brute force approach had to compare each interval with all others multiple times because there was no guarantee about which intervals might overlap. In contrast, once the intervals are sorted, overlapping intervals are always positioned next to each other, so a single pass is sufficient.

The time complexity of the first solution is O(n³), while the time complexity of the second solution is O(nlogn).The main issue with the brute force approach is that the intervals are in arbitrary order, which forces us to repeatedly go back and recheck them.To solve this efficiently, we first sort the intervals by their starting points in ascending order. After sorting, we know that each subsequent interval starts at a value greater than or equal to the previous one.Next, we create a result list and place the first interval into it. This list stores the intervals that have been merged so far.We then iterate through the remaining intervals one by one. For each new interval, we look at the last interval in the result list and ask one of two questions:

1)Does the new interval start before or exactly at the end of the last interval?

If the answer is yes, the intervals overlap. In that case, we extend the end of the last interval if the current interval ends later.

2. Do the intervals not overlap?

If they do not overlap, we simply append the new interval to the result list.

Edge Cases Considered

This solution correctly handles several important edge cases.

1. Empty input

if not intervals: return []

If the input is an empty list, the output is also an empty list, and the loop does not execute.

2.Only One Interval

merged=[intervals[0]]

In this case, the for loop does not run because there are no additional intervals to process.

3.All Intervals Overlap

Every new interval overlaps with the last merged interval, so the end point is continuously extended using last[1]=max…

4.No Intervals Overlap

The condition current[0]≤last[1] is always false, so each interval is added to the merged list separately.

5.Adjacent Intervals

Because we use ≤ instead of <, intervals that touch at their boundaries are also merged.

To strengthen your understanding of interval problems, try solving these related problems:

1. https://leetcode.com/problems/insert-interval/description/
2. https://leetcode.com/problems/non-overlapping-intervals/description/