Pattern #31

Merge Intervals

Important interview questions, thinking patterns, sorting by start time, single-pass merge scan, covered interval rules, and Go rules.

Must Solve

12 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.Interval List Intersections
Two Pointers: start=max(a,b), end=min(a,b), advance smaller endmedium
4.Non-overlapping Intervals
Greedy: Sort by end time + keep earliest finishing intervalmedium
5.Meeting Rooms
Sort by start time + check adjacent intervals overlapeasy
6.Meeting Rooms II
Sort by start time + Min Heap of end times (or Sweep Line)medium
7.Remove Covered Intervals
Sort by start ASC, end DESC + single pass max end checkmedium
8.Minimum Number of Arrows to Burst Balloons
Greedy: Sort by end time + shoot at earliest balloon endmedium
9.Employee Free Time
Merge all busy intervals + collect gaps between merged intervalshard
10.Divide Intervals Into Minimum Number of Groups
Same as Meeting Rooms II (Sort start + Min Heap end times)medium
11.Minimum Interval to Include Each Query
Sort queries & intervals + Min Heap storing (length, end)hard
12.My Calendar I
TreeMap / BST checking previous & next neighbor overlapsmedium

Also Important

8 more questions worth practicing.

13.My Calendar II
Track single & double booking intervals listmedium
14.Meeting Scheduler
Sort both slots + 2 pointers intersect window >= durationmedium
15.Car Pooling
Difference Array / Sweep Line for passenger capacitymedium
16.Flowers in Full Bloom
Binary Search start/end arrays or Sweep Line querieshard
17.Amount of New Area Painted Each Day
Segment Tree or Union-Find / Interval Treehard
18.Data Stream as Disjoint Intervals
TreeMap storing non-overlapping interval rangeshard
19.Range Module
Segment Tree or balanced BST interval merginghard
20.Video Stitching
Greedy farthest reach or DP interval coveragemedium

How to Think

Need combine overlapping ranges?Sort by START + Merge (cur.start <= last.end)
Intervals already sorted?Scan directly without extra sorting
Current interval overlaps last one?Check: current.start <= last.end
Overlap found?Update: last.end = max(last.end, current.end)
No overlap?Save current as a new separate interval

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 _, cur := range intervals[1:] {
        last := result[len(result)-1]

        // 2. Compare current.start <= last.end
        if cur[0] <= last[1] {
            if cur[1] > last[1] {
                last[1] = cur[1] // Merge: last.end = max(last.end, cur.end)
            }
        } else {
            result = append(result, cur) // Append new interval
        }
    }
    return result
}

👉 Total Time: O(N log N) | Scan: O(N) | Space: O(N)

Why Sort First?

Suppose input is [8,10], [2,6], [1,3]. Without sorting, finding which intervals overlap requires comparing every interval with every other interval (O(N²) time).

After sorting by start time [1,3], [2,6], [8,10], all overlapping intervals appear adjacent to each other! We only need to compare each interval with the LAST MERGED INTERVAL.

👉 Sorting turns an arbitrary 2D search into a single left-to-right scan in O(N log N) time!

Covered Interval Case ([1,10] & [2,5])

❌ Direct Assignment Mistake

Writing last.end = cur.end makes [1,10] + [2,5] become [1,5], accidentally shrinking the end boundary!

✅ Max End Assignment

Writing last.end = max(last.end, cur.end) keeps [1,10] intact!

Visual Memory Rule

1. Sort by START
2. Keep LAST merged interval
3. current.start <= last.end  → OVERLAP
4. Merge: last.end = max(last.end, current.end)
5. No overlap → Add new interval

💡 Golden Rule: "Sort by start, then compare every interval only with the last merged interval."

Common Interview Mistakes

1. Not Sorting First

Attempting to merge unsorted intervals. Always sort by start time first to ensure left-to-right single pass correctness!

2. Wrong Overlap Condition

Using current.end >= last.start instead of current.start <= last.end.

3. Replacing End Directly

Writing last.end = current.end instead of last.end = max(last.end, current.end) destroys covered interval ranges.

4. Comparing with Original Previous Interval

Comparing current interval with the original input interval instead of the LAST MERGED INTERVAL in the result slice!

Interview Rules

1. Overlapping ranges? → Merge Intervals
2. Sort first → by start time (O(N log N))
3. Compare condition → current.start <= last.end
4. Merge formula → last.end = max(last.end, current.end)
5. No overlap → append current as a new interval
6. Compare against → LAST MERGED interval in result array
7. Time Complexity → O(N log N) time, O(N) space
8. Production real systems → clarify boundary semantics ([start, end] vs [start, end))

Small Rules

Rule 1: Always sort by start time first.
Rule 2: Keep only the last merged interval for single-pass comparison.
Rule 3:Overlap occurs when current.start <= last.end.
Rule 4:No overlap occurs when current.start > last.end.
Rule 5: When merging, update last.end = max(last.end, current.end).
Rule 6: The start of the merged interval remains last.start (guaranteed by sorting).

Production Thinking

Calendar Busy Duration → Merge overlapping meetings to calculate total busy time without double counting

Server Outage Duration → Merge overlapping server downtime incidents for SLA compliance calculations

User Session Active Time → Merge overlapping user activity logs before computing active engagement metrics

Log Alert Deduplication → Merge overlapping alert windows to avoid rendering duplicate monitoring incidents

Remember This

Merge Intervals

1. Sort by START

2. Keep LAST merged interval

3. current.start <= last.end
   → OVERLAP

4. Merge:
   last.end = max(last.end, current.end)

5. No overlap
   → add new interval

Time
→ O(n log n)

💡 Golden Rule: "Sort by start, then compare every interval only with the last merged interval."