Merging Overlapping Intervals

Welcome back! In our last lesson, we delved into the intricacies of linked lists with the Fast and Slow Pointers pattern, a clever technique for cycle detection. Today, we'll switch our focus back to arrays and introduce a new, powerful algorithmic pattern: Merge Intervals.

This pattern is fundamental for solving a wide range of problems involving overlapping ranges. As an engineer with experience in system architecture, you've likely dealt with concepts like scheduling jobs, allocating resources, or consolidating time-series data. The Merge Intervals pattern provides the algorithmic foundation for handling these scenarios efficiently. In this lesson, we will implement the core pattern and then explore how it can be adapted to solve more complex, interview-style problems.

1. The Core Problem: Merging Overlapping Intervals

Imagine you have a list of time intervals, for example, [[1,4], [7,9], [3,6], [8,10]]. The task is to merge any intervals that overlap to produce a list of mutually exclusive intervals.

A brute-force approach might involve comparing every interval with every other interval, which would be inefficient, likely leading to an $O(N^2)$ time complexity. The key insight to an optimal solution is to first bring order to the input.

If we sort the intervals based on their start times, the problem becomes much simpler. After sorting, our example list becomes [[1,4], [3,6], [7,9], [8,10]]. Now, any potential overlaps will be between adjacent intervals in the sorted list.

The following video from NeetCode provides an excellent visual explanation of why sorting is so effective and walks through the general strategy.

2. The Merge Intervals Algorithm

Once the intervals are sorted by their start time, we can process them linearly to build our merged list. The algorithm is as follows:

1. Sort the input array of intervals based on their start values.
2. Create an output list and initialize it with the first interval from the sorted list.
3. Iterate through the rest of the sorted intervals, starting from the second one.
4. For the current interval being examined, compare it with the last interval in your output list.
   • If they overlap: The current interval's start is less than or equal to the last interval's end. We merge them by updating the end of the last interval in our output list to be the maximum of the two end times. (e.g., merging [1,4] and [3,6] results in [1,6]).
   • If they do not overlap: The current interval starts after the last interval has ended. We simply add the current interval to our output list as a new, distinct interval.
5. Repeat until all intervals are processed. The output list now contains the final merged intervals.

This image provides a great step-by-step visualization of the algorithm in action after sorting.

3. Implementation in Go and JavaScript

Now, let's translate this logic into code. Since you are proficient in both Go and JavaScript, we have excellent resources for both.

The following article provides a concise and clear implementation in Go, which aligns perfectly with your skill set.

For a JavaScript perspective and to see how the logic applies to slightly different data structures (like an Interval class), the resource below is very thorough.

The time complexity of this algorithm is $O(N\log N)$, which is dominated by the initial sorting step. The iteration itself is a single pass, which is $O(N)$. The space complexity is $O(N)$ in the worst case (if no intervals merge) to store the output. This is a significant improvement over the naive $O(N^2)$ approach.

4. Applying the Pattern: Common Variations

In interviews, you'll often be asked to solve problems that are variations of this core pattern. Your ability to recognize and adapt the pattern is what interviewers are looking for.

Variation 1: Conflicting Appointments

A common warm-up question is: "Given a list of appointments as intervals, determine if a person can attend all of them."

This is a simplified version of our problem. We don't need to produce a merged list; we just need to detect if any overlap exists.

Algorithm:

1. Sort the appointments by their start time.
2. Iterate through the sorted list from the second appointment.
3. If any appointment's start time is less than the previous appointment's end time (intervals[i].start < intervals[i-1].end), an overlap exists. You can immediately return false.
4. If the loop completes without finding any overlaps, return true.

Notice the strict inequality (<). If one appointment ends at the exact moment another begins (e.g., [2,4] and [4,5]), they don't conflict.

Variation 2: Minimum Meeting Rooms (A Harder Problem)

A more challenging and classic interview problem is: "Given a list of meeting intervals, find the minimum number of conference rooms required to hold all the meetings."

Simple merging isn't enough here. Merging [[9,10], [9:30, 11]] tells us they overlap, but we need to know the maximum number of concurrent meetings at any point in time. This is where we combine the Merge Intervals sorting strategy with another data structure: a Min-Heap (also known as a Priority Queue).

Algorithm:

1. Sort the meetings by their start time.
2. Initialize a Min-Heap to store the end times of the meetings currently in progress.
3. Initialize a counter for rooms, rooms = 0.
4. Iterate through the sorted meetings:
   a. Look at the meeting at the top of the Min-Heap (the one that ends the soonest). If the current meeting starts after or at the same time as this earliest-ending meeting finishes, it means a room has become free. Remove that end time from the heap.
   b. Add the end time of the current meeting to the heap. A new meeting is starting, so it occupies a room.
   c. Update your answer with the maximum size the heap has reached so far. This represents the peak number of concurrent meetings.
5. The final answer is the maximum size the heap attained during the process.

This problem is a fantastic example of combining patterns, something you'll definitely encounter as you design more complex systems.

Conclusion

In this lesson, we mastered the Merge Intervals pattern, a crucial technique for your algorithmic toolkit. We saw how a simple act of sorting transforms a complex problem into a manageable linear scan. This pattern is not just an abstract puzzle; it models real-world problems in scheduling, resource management, and data analysis that you will encounter in scalable backend systems.

Key Takeaways:

• The Core Idea: Sorting intervals by their start time is the critical first step to efficiently detect and merge overlaps.
• The Algorithm: After sorting, iterate through the intervals, comparing the current interval's start with the previous merged interval's end to decide whether to merge or append.
• Complexity: The solution has a time complexity of $O(N\log N)$ and space complexity of $O(N)$.
• Variations: The pattern can be adapted to answer related questions, such as detecting any conflict (Conflicting Appointments) or finding the peak resource usage (Minimum Meeting Rooms) by combining it with other data structures like a Min-Heap.

In our next lesson, we will explore the Cyclic Sort pattern. This is a unique and efficient pattern for problems involving arrays containing numbers in a specific range, often used to find missing or duplicate elements in-place.