Merge Intervals: Simplified

Heya, I’m back this week with another pattern for you. This pattern helped me pass my Big Tech interviews (although I had to turn it down, this a story for another time).

Ya'll I have to tell you a little story, so I wasn't getting any traction on my resume at all.

It was really depressing as prior to this year, anywhere that I would submit my resume, I'd get a call almost immediately.

I wondered what happened, what the hell was I doing wrong?

Then, I met Paul Dakessian and told him about my struggle.

He helped me fix my resume but not just fix it, I mean, 24 hours after we fixed it, I got 3 interview requests.

To say I am feeling better is an understatement.

If you need to get a job ASAP, this guy will fix your problem and help you get your job.

Check out his page here for more info, and when you reach out to him tell him Ricardo sent you. -> Get resume and interview help today.

When preparing for coding interviews, you'll often face array problems that require merging intervals. The Merge Intervals problem is one of the most common examples, and once you understand the basic technique, you can apply it to a variety of scenarios.

Let's break down how to approach this problem and solve it efficiently.

What Are Merge Intervals?

Given a collection of intervals, the task is to merge overlapping intervals. If two intervals overlap, you combine them into one. The goal is to return a list of non-overlapping intervals that cover all the intervals in the input.

Key Steps to Solve the Problem

1. Sort the intervals by their start times. Sorting helps us efficiently merge intervals in one pass.
2. Iterate through the sorted intervals and compare each interval with the last one we added to the result list. If they overlap, merge them by adjusting the end time.
3. Return the merged intervals after processing all the input.

Example

Let’s look at an example to make it clearer.

Input:

[[1, 3], [2, 6], [8, 10], [15, 18]]        

Output:

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

Here, the intervals [1, 3] and [2, 6] overlap, so they get merged into [1, 6]. The other intervals don't overlap, so they stay the same.

Why Do Intervals Overlap?

Two intervals overlap if the start of one interval is less than or equal to the end of the other. More specifically, if the second interval's start is less than or equal to the first interval's end, they are overlapping.

For example:

• The interval [1, 3] represents a range that starts at 1 and ends at 3.
• The interval [2, 6] represents a range that starts at 2 and ends at 6.

These two intervals overlap because the second interval [2, 6] starts before the first interval [1, 3] ends. More clearly:

• The end of the first interval is 3.
• The start of the second interval is 2.

Since 2 is less than or equal to 3, there is an overlap. This is why the intervals [1, 3] and [2, 6] need to be merged. They get combined into a single interval [1, 6], covering the entire range from the start of the first interval to the end of the second.

Code Example

Let’s walk through how to do this in Python:

def merge(intervals):
    # Step 1: Sort the intervals by the start time
    intervals.sort(key=lambda x: x[0])

    # Step 2: Initialize the result list
    merged = []

    # Step 3: Iterate through each interval
    for interval in intervals:
        # If the list is empty or there is no overlap, just add the interval
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # If there's an overlap, merge the intervals by updating the end time
            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged        

Simple Walkthrough

• Sort the intervals. Sorting ensures that we process them in order, making it easy to detect overlaps.
• Iterate through each interval. If the list is empty or the current interval doesn’t overlap with the last one in merged, we simply add it.
• Merge overlapping intervals by adjusting the end time of the last interval.

A More Visual Example

Imagine the input is [[1, 3], [2, 6], [8, 10], [15, 18]].

• First, sort the intervals: [[1, 3], [2, 6], [8, 10], [15, 18]].
• Start with [1, 3] and compare it with [2, 6]. Since they overlap, merge them into [1, 6].
• Compare [8, 10] with [1, 6]. No overlap, so add it as-is.
• Compare [15, 18] with [8, 10]. No overlap, so add it as-is.

The final result is: [[1, 6], [8, 10], [15, 18]].

Edge Cases to Consider

• Empty input: If no intervals are given, return an empty list.

# Input: [] # Output: []        

• Single interval: If only one interval is provided, return it as-is.

# Input: [[2, 3]] # Output: [[2, 3]]        

• No overlaps: If none of the intervals overlap, just return the sorted list.

# Input: [[1, 2], [3, 4], [5, 6]] # Output: [[1, 2], [3, 4], [5, 6]]        

Some Takeaways

• Sorting is essential to solving the problem efficiently.
• Merge intervals by adjusting the end time whenever there’s an overlap.
• The time complexity of this approach is O(n log n) due to the sorting step, with a linear pass for merging.

Let’s solve Merge Intervals (Leetcode Medium) to show the use of this technique a little more.

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

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
        

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
        

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Solution

function merge(intervals: number[][]): number[][] {

    // Step 1: Sort the intervals by the start time

    intervals.sort((a, b) => a[0] - b[0]);

    // Step 2: Initialize the result list
    const merged: number[][] = [];

    // Step 3: Iterate through each interval

    for (let interval of intervals) {

        // If merged list is empty or there is no overlap, just add the interval

        if (merged.length === 0 || merged[merged.length - 1][1] < interval[0]) {
            merged.push(interval);
        } else {

            // If there's an overlap, merge the intervals by updating the end time

            merged[merged.length - 1][1] = Math.max(merged[merged.length - 1][1], interval[1]);
        }
    }

    // Step 4: Return the merged list
    return merged;
}
        

Let me explain what’s going on here:

1. Sorting: The intervals are sorted by their starting times. This helps us efficiently merge overlapping intervals by comparing each interval to the last one added to the result list.

intervals.sort((a, b) => a[0] - b[0]);        

1. Iterating and Merging:
2. Return the Result: After merging, return the list of merged intervals.

Time Complexity:

• Sorting the intervals takes O(n log n).
• Merging the intervals takes O(n).

Thanks!

Please like and share this newsletter for me!