Pattern 4: Merge Intervals

Deep Dive: Interval Operations Visualized

Merge Overlapping Intervals

Input:  |---1---|      |--3--|     |---5---|
            |----2----|       |4|
        
Sorted: [1,3] [2,6] [4,5] [8,10] [15,18]

Step 1: [1,3] -> start result [[1,3]]
Step 2: [2,6] overlaps (2<=3) -> merge to [1,6]
Step 3: [4,5] overlaps (4<=6) -> merge to [1,6] (6>5 so no change)
Step 4: [8,10] no overlap (8>6) -> add. result: [[1,6],[8,10]]
Step 5: [15,18] no overlap -> add. result: [[1,6],[8,10],[15,18]]

Sweep Line -- Meeting Rooms II

"How many rooms needed for meetings [[0,30],[5,10],[15,20]]?"

Events: (0,+1) (5,+1) (10,-1) (15,+1) (20,-1) (30,-1)
Sorted: 0:+1  5:+1  10:-1  15:+1  20:-1  30:-1

Time:  0   5   10   15   20   30
Count: 1   2    1    2    1    0
Max simultaneous = 2 -> need 2 rooms

---

Signal: Overlapping intervals, scheduling, calendar conflicts Template: merge_intervals() in templates.py

When to Use

• "Merge overlapping intervals" -> sort by start
• "Maximum non-overlapping" -> sort by end (greedy)
• "Conference rooms needed" -> sweep line (start=+1, end=-1)
• "Insert new interval"

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Merge Intervals	Phase 2.6	15 min	[ ]
Non-overlapping Intervals	Phase 5.4	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Intervals / ranges / time slots that may overlap" — pairs of (start, end) in the input is the giveaway.
• "Calendar / meeting room / scheduling conflicts" — the prompt literally talks about overlap or conflict.
• "Insert a new interval into a sorted list and merge as needed" — pure variation of the canonical merge.
• "Minimum number of resources / rooms / CPUs / platforms needed concurrently" — sweep line over interval start (+1) and end (−1) events.
• "Find free slots / gaps between busy intervals" — same input shape, just reporting the complement.

Anti-signals (looks like this pattern, isn't)

• "Maximum number of non-overlapping intervals you can keep" — same input shape, but solved by Greedy (sort by end, not by start). Different sort key, different mental model.
• "Range-sum or range-update queries on numeric ranges" — that is Prefix Sum / Segment Tree / Difference Array, not interval merge.
• "K closest intervals to a point" — Heap problem, not interval merge.