The Merge Intervals pattern is a common algorithmic technique used to deal with overlapping or intersecting intervals. The core idea is to sort the intervals based on their start times and then iterate through them, merging any overlapping intervals.

Core Idea:

  1. Sort: Sort the intervals based on their starting points. If two intervals have the same starting point, sort them by their ending points (though sorting by start is usually sufficient).
  2. Iterate and Merge:
    • Initialize an empty list merged_intervals.
    • Add the first interval from the sorted list to merged_intervals.
    • Iterate through the rest of the sorted intervals:
      • Let the last_merged_interval be the last interval in merged_intervals.
      • Let the current_interval be the interval you are currently processing.
      • If the current_interval overlaps with the last_merged_interval (i.e., current_interval.start <= last_merged_interval.end), then merge them by updating the end of last_merged_interval to be max(last_merged_interval.end, current_interval.end).
      • Otherwise (if there’s no overlap), add the current_interval to merged_intervals.

Common Scenarios & How it Works:

  1. Merging Overlapping Intervals (e.g., LeetCode #56): This is the most direct application. Given a collection of intervals, merge all overlapping intervals.
  2. Inserting a New Interval (e.g., LeetCode #57): Given a set of non-overlapping intervals and a new interval, insert the new interval into the correct position and merge if necessary. The approach involves finding where the new interval fits, then merging with any overlapping intervals before and after its insertion point.
  3. Finding Non-overlapping Intervals / Free Time (e.g., LeetCode #759 - Employee Free Time): After merging all busy/booked intervals, the gaps between the merged intervals represent the non-overlapping or free time slots.
  4. Checking for Conflicts (e.g., Meeting Rooms II - LeetCode #253): Determine the minimum number of conference rooms required. This can be solved by sorting start and end times separately or by using a min-heap to track end times of ongoing meetings. If intervals are sorted by start times, when considering a new interval, if it overlaps with the earliest ending meeting, a new room is needed.
  5. Interval Intersection (e.g., LeetCode #986): Given two lists of intervals, find their intersection. This often involves a two-pointer approach on the sorted interval lists.

Advantages:

  • Efficiency: Sorting takes O(N log N) time, and the merging process takes O(N) time. So, the overall time complexity is typically O(N log N).
  • Simplicity: The logic, once understood, is relatively straightforward to implement.
  • Versatility: Applicable to a wide range of interval-based problems.

When to Use:

  • Problems involving scheduling, resource allocation, or time management where you have a set of events or tasks represented by intervals.
  • When you need to consolidate or find gaps between ranges of data.
  • Geometric problems that can be reduced to 1D interval problems.

Example LeetCode Problems:

  1. (#56) Merge Intervals
  2. (#57) Insert Interval
  3. (#252) Meeting Rooms
  4. (#253) Meeting Rooms II
  5. (#435) Non-overlapping Intervals
  6. (#986) Interval List Intersections
  7. (#759) Employee Free Time