DSA Pattern - Merge Intervals

Hey guys,

Today let’s discuss Merge Intervals.

This pattern is a common pattern used in many problems where you have a collection of intervals and you need to merge all overlapping intervals into a smaller number of intervals.

I’ll explain Merge Intervals in detail below:

Imagine You Have a Bunch of Time Slots:

• Think of each interval as a time slot, like [2, 4] means something is happening from time 2 to time 4.

Goal: Make a Simpler Schedule:

• Your job is to combine these time slots into fewer slots if they overlap. For example, if one event is from 2 to 4 and another from 3 to 5, you can make it one big event from 2 to 5.

How to Do It:

1. Sort the Slots:First, arrange the time slots in order, starting with the earliest one. It's like sorting your daily schedule from morning to night.
2. Combine Overlapping Slots:Go through your sorted schedule. If one event overlaps with the next (like one ends at 4 and the next starts at 3), combine them into a single time slot.Keep doing this for all events.

Example:

• You have these time slots: [1, 3], [2, 6], [8, 10], [15, 18].
• After sorting, they stay the same because they are already in order.
• Now, look at the first two: [1, 3] and [2, 6]. They overlap because the first ends at 3, and the second starts at 2. So, you combine them into [1, 6].
• The next slots [8, 10] and [15, 18] don’t overlap with anything, so they stay the same.
• Your final schedule is: [1, 6], [8, 10], [15, 18].

The key steps to merge intervals are sorting the intervals and then combining the overlapping ones.

Let’s do a Leetcode medium problem today.

Merge Intervals

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        

Answer:

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

    // Step 1: Sort the intervals based on the start time.
    intervals.sort((a, b) => a[0] - b[0]);

    // The merged array will store our final merged intervals.
    const merged: number[][] = [];

    // Step 2: Iterate through each interval.
    for (let i = 0; i < intervals.length; i++) {

    // If the merged array is empty or the current interval does not overlap with the last interval in merged, just add it to merged.

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

            // If there is an overlap, merge the current interval with the last interval in merged.
            // We do this by updating the end time of the last interval in merged.

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

    // Return the array of merged intervals.
    return merged;
}

// Example usage:
const intervals1 = [[1, 3], [2, 6], [8, 10], [15, 18]];
console.log(merge(intervals1)); // Output: [[1, 6], [8, 10], [15, 18]]

const intervals2 = [[1, 4], [4, 5]];
console.log(merge(intervals2)); // Output: [[1, 5]]        

Function Definition: We define a function merge that takes an array of intervals.

Sorting Intervals: The intervals are sorted based on their start time. This makes it easier to find overlapping intervals.

Creating a Merged Array: This array will store the final merged intervals.

Iterating Through Intervals: We use a for loop to go through each interval in the sorted list.

Check for Overlap:

• If the merged array is empty or if the current interval does not overlap with the last interval in the merged array (i.e., the start of the current interval is greater than the end of the last interval in merged), we add the current interval to the merged array.
• If there is an overlap, we merge the current interval with the last interval in the merged array by updating the end time of the last interval in merged to be the maximum of its own end time and the end time of the current interval.

Returning the Result: After all intervals are processed, we return the merged intervals.

Example Usage: We test the function with two examples and log the outputs to the console.

If you like this type of content, subscribe -> https://thenewdevs.substack.com/