Merge Intervals

What you'll learn

• The Golden Rule

  When to use interval patterns: Any time you encounter problems involving time ranges, overlapping ranges, scheduling, or any data represented as start/end pairs, reach for interval techniques. Common signals in problem statements: - "Giv…

• Core Concepts

• Sorting Strategy

  Almost every interval problem begins with sorting by start time. This transforms a chaotic list into a sequential timeline where you only need to compare each interval with its immediate neighbors or a running state. After sorting, overl…

• Overlap Detection

  Two intervals A = [astart, aend] and B = [bstart, bend] overlap if and only if: Equivalently, they do NOT overlap if one ends before the other starts: When intervals are sorted by start time and we process them sequentially, the overlap…

• Merging Two Overlapping Intervals

  When two intervals overlap, their merge is: If already sorted by start, A.start

• Alternative: Difference Array (for integer time)

  When time values are integers within a bounded range, use a difference array for O(n + T) where T is the time range.

• Complexity

  | Approach | Time | Space | |----------|------|-------| | Two-pointer sweep | O(n log n) | O(n) | | Difference array | O(n + T) | O(T) |

• When to Use Which

  - Two-pointer: When time values are floating point or the range is very large - Difference array: When time is integer and range is bounded (very simple to implement) ---

• Key Takeaways

  - Sort first (by start for merging, by end for greedy selection) - Overlap condition after sorting by start: current.start <= previous.end - Sweep line for counting concurrency - Two pointers for intersection of two sorted lists - Greedy…