Merge Intervals Pattern

Merge Intervals

Problem Scenario / Typical Use Case

Imagine you are managing room bookings in a hotel, and you want to combine overlapping bookings to determine which time slots are actually occupied.

Checking each interval against all others is inefficient. The Merge Intervals pattern provides a systematic way to sort and merge overlapping ranges, simplifying complex schedule or range management problems.

Basic Idea

The Merge Intervals pattern involves sorting intervals by start time and iterating through them while merging overlaps:

1. Sort intervals by start time.
2. Compare the current interval with the last merged interval.
3. If they overlap, merge them into a single interval; otherwise, add the current interval to the merged list.

Typical operations include:

• Combining overlapping time slots.
• Calendar availability analysis.
• Simplifying range data for computation.

Advantages

• Simplicity: Once sorted, the merge logic is straightforward.
• Efficiency: Time complexity is (O(n \log n)) due to sorting, which is optimal for comparison-based sorting.
• Versatility: Works with time ranges, numeric ranges, or any comparable intervals.

Limitations / Considerations

• Sorting is required; for very large datasets, consider memory and sorting cost.
• Only works for intervals with comparable start and end points.
• Edge cases like zero-length intervals or fully nested intervals require careful handling.

Practical Examples / Thought Triggers

1. Room Booking Overlaps: Merge overlapping bookings to see which hours are actually occupied.
2. Employee Schedule Management: Combine shifts to find free or busy periods efficiently.
3. Numeric Range Simplification: Merge ranges of IP addresses, numeric constraints, or priority intervals.

Thought Triggers:

• Do intervals need to be sorted first? Sorting defines the merging order.
• How should exact overlaps (e.g., end equals start) be handled?
• Can this be combined with other patterns like Two Pointers for optimized range queries?

Implementation Example

Here’s a Python example for merging overlapping intervals:

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

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

    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:  # overlap
            last[1] = max(last[1], current[1])  # merge
        else:
            merged.append(current)

    return merged

# Example usage
bookings = [[1, 3], [2, 6], [8, 10], [9, 12]]
print(merge_intervals(bookings))
# Output: [[1, 6], [8, 12]]

This demonstrates merging logic: efficiently combining overlapping intervals after sorting.

Related Articles

• Sorting-Based Patterns: Merge Intervals relies on initial sorting to simplify comparisons.
• Two Pointers: Can sometimes be used to iterate and merge ranges more efficiently.
• Greedy Algorithms: The decision to merge the current interval with the last can be seen as a greedy choice.