Pattern #30

Intervals

Important interview questions, thinking patterns, sorting by start vs end, Meeting Rooms II min heap, Sweep Line algorithm, and Go rules.

Must Solve

15 core questions — solve these first.

1.Merge Intervals
Sort by start time + single pass merge (current.start <= last.end)medium
2.Insert Interval
3 parts: before (copy), overlapping (merge min start/max end), after (copy)medium
3.Non-overlapping Intervals
Greedy: Sort by end time + keep earliest finishing intervalmedium
4.Meeting Rooms
Sort by start time + check adjacent intervals overlapeasy
5.Meeting Rooms II
Sort by start time + Min Heap of end times (or Sweep Line)medium
6.Minimum Number of Arrows to Burst Balloons
Greedy: Sort by end time + shoot at earliest balloon endmedium
7.Interval List Intersections
Two Pointers: start=max(a,b), end=min(a,b), advance smaller endmedium
8.Employee Free Time
Merge all busy intervals + collect gaps between merged intervalshard
9.Remove Covered Intervals
Sort by start ASC, end DESC + single pass max end checkmedium
10.Meeting Scheduler
Sort both slots + 2 pointers intersect window >= durationmedium
11.My Calendar I
TreeMap / BST checking previous & next neighbor overlapsmedium
12.My Calendar II
Track single & double booking intervals listmedium
13.Minimum Interval to Include Each Query
Sort queries & intervals + Min Heap storing (length, end)hard
14.Divide Intervals Into Minimum Number of Groups
Same as Meeting Rooms II (Sort start + Min Heap end times)medium
15.Maximum Number of Events That Can Be Attended
Sort events by start day + Min Heap of active event end daysmedium

Also Important

9 more questions worth practicing.

16.My Calendar III
Sweep Line TreeMap event count (+1 start, -1 end)hard
17.Car Pooling
Difference Array / Sweep Line for passenger capacitymedium
18.Corporate Flight Bookings
Difference Array prefix sum for seat bookingsmedium
19.Amount of New Area Painted Each Day
Segment Tree or Union-Find / Interval Treehard
20.Flowers in Full Bloom
Binary Search start/end arrays or Sweep Line querieshard
21.Range Module
Segment Tree or balanced BST interval merginghard
22.Data Stream as Disjoint Intervals
TreeMap storing non-overlapping interval rangeshard
23.Minimum Number of Taps to Open to Water a Garden
Jump Game II DP / Greedy farthest reachhard
24.Video Stitching
Greedy farthest reach or DP interval coveragemedium

How to Think

Problem gives [start, end] ranges?Intervals Pattern
Need combine overlapping ranges?Sort by START + Merge (cur.start <= last.end)
Need maximum non-overlapping intervals?Sort by END + Greedy (earliest finish)
Need minimum rooms / resources?Sort by START + Min Heap of end times OR Sweep Line
Need intersection of two interval lists?Two Pointers (start=max(a,b), end=min(a,b))
Many start/end events over time?Sweep Line (+1 start, -1 end)

Go Merge Intervals Code Template

Standard Merge Intervals in Go

import "sort"

func merge(intervals [][]int) [][]int {
    if len(intervals) <= 1 {
        return intervals
    }

    // 1. Sort by Start Time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    result := [][]int{intervals[0]}

    for i := 1; i < len(intervals); i++ {
        last := result[len(result)-1]
        cur := intervals[i]

        // 2. Overlap check: cur.start <= last.end
        if cur[0] <= last[1] {
            if cur[1] > last[1] {
                last[1] = cur[1] // Merge: extend end to max(last.end, cur.end)
            }
        } else {
            result = append(result, cur) // No overlap: append new interval
        }
    }
    return result
}

👉 Time: O(N log N) (due to sorting) | Space: O(N)

Which Field to Sort? (Golden Decision Rule)

Sort by START Time

Use for Merge Intervals, Meeting Rooms I & II, and Employee Free Time. Processes events in chronological arrival order.

Sort by END Time

Use for Greedy Non-overlapping Intervals, Activity Selection, and Minimum Balloons Arrows. Finishing earliest leaves max space!

Sweep Line Algorithm (+1 / -1 Events)

Instead of storing full 2D intervals, convert each interval into two 1D events: (start, +1) and (end, -1).

type Event struct {
    time int
    val  int // +1 for start, -1 for end
}

// Sort events by time ASC (if equal time, end -1 comes before start +1 if boundary touching is allowed!)
sort.Slice(events, func(i, j int) bool {
    if events[i].time == events[j].time {
        return events[i].val < events[j].val
    }
    return events[i].time < events[j].time
})

activeRooms := 0
maxRooms := 0
for _, e := range events {
    activeRooms += e.val
    if activeRooms > maxRooms {
        maxRooms = activeRooms
    }
}

👉 Peak running sum = maximum simultaneous active overlapping intervals!

Visual Memory Rule

Merge Intervals      → Sort by START (cur.start <= last.end -> merge end = max(ends))
Greedy Scheduling    → Sort by END (earliest finish leaves max future room)
Meeting Rooms II     → Sort START + Min Heap of end times OR Sweep Line
Intersection         → start = max(starts), end = min(ends)

💡 Golden Rule: "For interval problems, first decide the ordering, then ask: overlap, finish early, or count active ranges?"

Common Interview Mistakes

1. Not Sorting First

Trying to merge or process unsorted intervals. Always sort first! Sorting turns a 2D problem into a single pass 1D scan.

2. Sorting by Wrong Field

Sorting by start time for Greedy Non-overlapping Intervals (fails!). Non-overlapping scheduling requires sorting by END time.

3. Losing the Larger End on Merge

When merging [1, 10] and [2, 5], setting end to 5 instead of max(10, 5) = 10 drops coverage!

4. Confusing Merge with Intersection

Merge takes min(starts), max(ends) $\to$ [1, 7]. Intersection takes max(starts), min(ends) $\to$ [3, 5].

Interview Rules

1. Ranges [start, end]? → Intervals Pattern
2. Merge overlaps? → Sort by START time (cur.start <= last.end)
3. Merge end formula → last.end = max(last.end, cur.end)
4. Max non-overlapping / Min arrows? → Sort by END time + Greedy choice
5. Minimum rooms / resources? → Sort by START + Min Heap of end times OR Sweep Line
6. Two interval lists intersection? → Two Pointers (start=max(starts), end=min(ends))
7. Sweep Line algorithm → Convert to events (start, +1) and (end, -1)
8. Boundary touching rule → Verify if [1,3] and [3,5] overlap (< vs <=) per problem description

Small Rules

Rule 1: Always sort first — sorting turns unordered 2D interval checks into a simple 1D scan.
Rule 2: Check problem boundary definitions for touching points ([1,3] and [3,5]).
Rule 3: Merging end is always max(last.end, cur.end).
Rule 4: Intersection range is always [max(starts), min(ends)].
Rule 5: For scheduling max activities, choosing the earliest finishing interval is the optimal greedy strategy.

Production Thinking

Calendar Meeting Scheduling → Detect calendar conflicts and find open meeting slots using interval merges

Hotel / Room Booking Occupancy → Compute peak room occupancy via Sweep Line (+1 check-in, -1 check-out)

Distributed Job Concurrency → Calculate peak worker pool capacity with Min Heap of job completion times

Employee Free Time Gap Finder → Merge team busy intervals to extract common free meeting windows

Remember This

Merge                 → Sort by START
Schedule / Greedy     → Sort by END
Overlap               → current.start <= last.end
Merge                 → max(end)
Intersection          → max(start), min(end)
Rooms                 → Min Heap of end times
Concurrent intervals  → Sweep Line
Two sorted lists      → Two Pointers

💡 Golden Rule: "For interval problems, first decide the ordering, then ask: overlap, finish early, or count active ranges?"