Cracking the Coding Interview: Part 5 – The Merge Intervals Pattern

Before diving into this next technique, if you're preparing for coding interviews and want a comprehensive resource, be sure to explore the Top 10 Essential Books for Cracking Coding Interviews (Ranked from Beginner to Advanced). These books are essential for anyone determined to land a job at top tech companies.

Overview of the Merge Intervals Pattern

The Merge Intervals pattern is a crucial technique used in solving problems that involve overlapping intervals or ranges. It’s commonly applied to tasks that involve merging schedules, summarizing ranges, or optimizing resource allocation by handling multiple intervals efficiently. This pattern ensures that overlapping intervals are combined into a single interval, thereby reducing redundancy and simplifying the overall problem.

When to Use the Merge Intervals Pattern:

• The problem involves a collection of intervals or ranges.
• You need to merge overlapping intervals or detect overlaps.
• You need to find free slots or gaps between intervals.
• The problem requires optimizing or simplifying intervals for tasks like scheduling.

Steps to Implement the Merge Intervals Pattern

1. Sort the intervals: To efficiently merge overlapping intervals, start by sorting the intervals based on their starting points. This ensures that you only need to compare consecutive intervals.

2. Merge overlapping intervals: As you traverse through the sorted list, check whether the current interval overlaps with the previous one. If it does, merge them into a single interval.

3. Return the merged list: After processing all intervals, return the newly merged list of intervals.

Example Problems Using the Merge Intervals Pattern

1. Merging Overlapping Intervals

Problem: Given a collection of intervals, merge all overlapping intervals.

def merge_intervals(intervals):
    if not intervals:
        return []

    # Sort intervals by their start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for i in range(1, len(intervals)):
        # If the current interval overlaps with the last interval in merged list
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])

    return merged

Explanation:

• First, we sort the intervals based on their start time.
• Then, for each interval, we check if it overlaps with the previously merged interval.
• If it does, we merge the two by adjusting the end time. Otherwise, we add the current interval to the result list.

This reduces the problem from O(n²) to O(n log n) due to the sorting step.

2. Inserting an Interval

Problem: Given a sorted list of non-overlapping intervals and a new interval, insert the new interval into the list, merging it if necessary.

def insert_interval(intervals, new_interval):
    merged = []
    i = 0
    n = len(intervals)

    # Add all intervals that end before the new interval starts
    while i < n and intervals[i][1] < new_interval[0]:
        merged.append(intervals[i])
        i += 1

    # Merge all overlapping intervals with the new interval
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1

    merged.append(new_interval)

    # Add remaining intervals
    while i < n:
        merged.append(intervals[i])
        i += 1

    return merged

Explanation:

• First, we add all intervals that don't overlap with the new interval.
• Then, we merge any intervals that overlap with the new interval.
• Finally, we add the remaining intervals that come after the new interval.

This approach handles both the insertion and the merging of intervals in O(n) time.

3. Meeting Rooms (Checking for Overlaps)

Problem: Given a list of meeting intervals, determine if a person can attend all meetings (i.e., no meetings overlap).

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])

    for i in range(1, len(intervals)):
        # Check if there is an overlap between consecutive intervals
        if intervals[i][0] < intervals[i - 1][1]:
            return False

    return True

Explanation:

• We sort the intervals by start time.
• Then, we check if any two consecutive intervals overlap. If they do, it means the person cannot attend all meetings.

This solution runs in O(n log n) time due to the sorting step.

Key Benefits of the Merge Intervals Pattern

• Efficiency: Sorting the intervals upfront allows us to merge or process intervals efficiently, often reducing complex problems to linear time after the sort.
• Simplicity: The pattern uses simple comparisons and merges, making it easy to implement while handling complex scenarios.
• Versatility: This pattern applies to a wide range of real-world problems, such as scheduling, allocating resources, or finding gaps between events.

Common Interview Questions Using Merge Intervals

1. Merge Intervals

Problem: Merge a list of overlapping intervals.
Solution: Sort intervals by start time and merge overlapping intervals as described above.

2. Meeting Rooms II

Problem: Given a list of meeting intervals, find the minimum number of meeting rooms required.
Solution: Use a variation of the merge intervals pattern to count the number of overlapping meetings at any given time.

3. Employee Free Time

Problem: Given a schedule of employee intervals, find the free time slots common across all employees.
Solution: Merge overlapping intervals for each employee, then find gaps between the merged intervals.

Merge Intervals Hacks for Interviews

• Think about sorting first: In most merge intervals problems, sorting the intervals based on their start time simplifies the logic for merging overlapping intervals.
• Consider edge cases: Always check for cases where there are no overlaps, or where all intervals overlap, to ensure your solution handles both extremes.
• Keep track of intervals carefully: Be mindful of whether you're working with closed or open intervals (i.e., whether intervals include or exclude their endpoints).

Conclusion

The Merge Intervals pattern is a must-have tool for solving problems involving overlapping intervals, schedules, or ranges. Mastering this technique will allow you to handle complex problems with ease and efficiency, reducing time complexity from quadratic to linear with sorting.

In the next article, we’ll delve into the Cyclic Sort Pattern, another powerful tool used for solving array-based problems that involve finding missing numbers or handling unsorted data.

Stay tuned for Part 6!