Merge Intervals Pattern

The merge intervals pattern is a foundational algorithm for efficiently consolidating overlapping ranges, a common operation in systems that handle time-based data. Whether you're building a calendar application, resolving scheduling conflicts, or consolidating sensor data, mastering this technique is crucial. In technical interviews, it's a classic pattern that tests your ability to manipulate complex data with simple, elegant logic, separating competent coders from exceptional problem-solvers.

What is the Merge Intervals Pattern?

At its core, the merge intervals pattern is a method for transforming a collection of potentially overlapping intervals into a set of disjoint intervals (intervals that do not overlap). An interval is typically defined as a pair [start, end], where start <= end. The fundamental goal is to merge any two intervals where the start of one is less than or equal to the end of the other.

The pattern’s power lies in a simple pre-processing step: sorting. By first sorting the list of intervals by their start time, you transform a seemingly chaotic problem into one with linear, predictable logic. Once sorted, you can traverse the list just once, comparing each interval to the last one in your merged result to decide whether to extend the current range or start a new one.

The Core Algorithm: Step-by-Step

Let's break down the standard merging process using a concrete example. Suppose you are given intervals: [[1,3], [2,6], [8,10], [15,18]].

1. Sort by Start Time: The first step is to sort the intervals based on their starting value. In our example, they are already sorted: [[1,3], [2,6], [8,10], [15,18]]. Sorting is critical because it guarantees that any interval that can be merged will become adjacent in the list.

1. Initialize a Merged List: Create an empty list (or array) to hold the final, merged intervals. Let's call it merged.

1. Iterate and Compare: Traverse each interval in the sorted list.

• For the first interval [1,3], the merged list is empty, so simply add it: merged = [[1,3]].
• Take the next interval, [2,6]. Compare it to the last interval in merged, which is [1,3].
• Check for Overlap: Does the current interval ([2,6]) overlap with the last merged one ([1,3])? Overlap exists if current.start <= last.end. Here, 2 <= 3 is true. Therefore, they overlap.
• Merge: To merge, you don't add a new interval. Instead, you extend the end of the last merged interval. The new end becomes the maximum of the two ends: last.end = max(last.end, current.end). So, [1,3] becomes [1, max(3, 6)] = [1,6]. Now merged = [[1,6]].
• Next interval: [8,10]. Compare to last merged [1,6]. 8 <= 6? No. There is no overlap.
• No Overlap: Add the current interval as a new entry to merged: merged = [[1,6], [8,10]].
• Final interval: [15,18]. Compare to last merged [8,10]. 15 <= 10? No. No overlap. Add it: merged = [[1,6], [8,10], [15,18]].

The final merged, non-overlapping output is [[1,6], [8,10], [15,18]]. The key formula for merging is: if current.start <= previous.end, then previous.end = max(previous.end, current.end).

Key Variations and Applications

The basic merge logic serves as a template for several common variations you'll encounter.

1. Inserting a New Interval

Given a list of non-overlapping intervals sorted by start time, insert a new interval and merge if necessary. The efficient approach is to traverse the list, adding all intervals that end before the new one starts, then merging all overlapping intervals by continuously updating the new interval's start and end, and finally adding the remaining intervals. This avoids the brute-force method of adding and re-sorting the entire list.

2. Finding the Intersection of Two Interval Lists

Given two lists of disjoint intervals sorted by start time, find their intersection. For example, the intersection of [[1,3], [5,9]] and [[2,5], [7,10]] is [[2,3], [7,9]]. The technique uses a two-pointer iteration. For two intervals a and b, the intersection is [max(a.start, b.start), min(a.end, b.end)], provided that max(start) <= min(end). You then advance the pointer pointing to the interval with the smaller end time.

3. Checking for Meeting Conflicts

A direct application is determining if a person can attend all meetings, given an array of meeting time intervals [start, end]. This is simply the merge intervals problem in disguise: if you can merge the list and the number of intervals decreases, there was an overlap (conflict). More efficiently, after sorting, you just need to check if any adjacent intervals overlap by checking if meetings[i].start < meetings[i-1].end. If true, a conflict exists.

These patterns are ubiquitous in real applications. Calendar applications (like Google Calendar) use merging to display consolidated free/busy times. Scheduling systems use it to allocate resources without conflicts. In data processing, it's used for range consolidation, such as merging IP address ranges or genomic data segments.

Common Pitfalls

Failing to avoid these mistakes can break your algorithm or lead to inefficient solutions.

1. Skipping the Initial Sort: This is the most critical step. Attempting to merge intervals without first sorting by the start time leads to a flawed algorithm that will miss non-adjacent overlaps and require complex, nested loops. Always sort first.

1. Incorrect Overlap Check and Merge Logic: A common logical error is using the wrong comparison or update rule.

• Wrong: Checking if current.start <= current.end (this is always true).
• Wrong: Checking if current.start <= previous.start.
• Correct: Check if current.start <= previous.end.
• When merging, remember to use the maximum of the two ends: max(previous.end, current.end). Using only current.end fails if the previous interval extends farther.

1. Ignoring Edge Cases: Robust code handles edge cases gracefully. Always consider:

• An empty list of intervals.
• A list with a single interval.
• Intervals that are completely contained within another (e.g., [1,10] and [2,5]). Your max() logic should handle this.
• Non-standard input, like intervals where start > end. Clarify with your interviewer, but typically you would validate or normalize the input first.

1. Modifying the Input List In-Place: While sometimes acceptable, it's often safer to create a new merged result list. Modifying the input list while iterating over it can lead to index errors and confusing code. Explicitly building a new output list is clearer and avoids side effects.

Summary

• The merge intervals pattern solves overlap problems by first sorting intervals by their start time and then linearly merging adjacent intervals where the start of one is less than or equal to the end of the previous.
• The core merging logic is a conditional check: if current.start <= previous.end, update previous.end = max(previous.end, current.end); otherwise, append the current interval as a new entry.
• Major variations include inserting a new interval into a sorted list, finding the intersection between two interval lists, and checking for conflicts in a schedule.
• This pattern is essential for real-world features like calendar rendering, resource scheduling, and data range consolidation, making it a high-frequency topic in coding interviews for software engineering roles.
• Avoid critical pitfalls by always remembering to sort, using the correct overlap comparison and max() function for merging, and carefully handling edge cases like empty lists or fully contained intervals.