Blind 75 — Interval Pattern Guide

How to Identify an “Interval” Problem

Interview Triggers

• Input is a list of [start, end] pairs
• “Merge overlapping…”, “insert into sorted intervals…”
• “Schedule meetings”, “meeting rooms”, “minimum rooms needed”
• “Remove minimum intervals so the rest don’t overlap”
• “Can a person attend all meetings?”

Which Sub-Pattern Does It Belong To?

If the prompt says…	Use this sub-pattern	Example LC
Insert new interval, return merged list	Linear merge in 3 phases	57
Merge overlapping intervals	Sort by start + merge	56
Min intervals to remove for non-overlap	Greedy: keep earliest end	435
Can attend all meetings? (true/false)	Sort + adjacency check	252
Minimum meeting rooms needed	Min-heap of end times OR sweep line	253

---

The Decision Tree

INTERVAL PROBLEM
│
├─ Need to MERGE / consolidate?
│   ├─ Given list                → Sort by start, walk + merge (LC 56)
│   └─ Insert one into sorted    → 3-phase linear scan (LC 57)
│
├─ Need to COUNT or remove for non-overlap?
│   └─ Sort by END, greedy keep  → LC 435
│
├─ Need to detect overlap?
│   └─ Sort by start, check adj  → LC 252
│
└─ Need MAX concurrent intervals (rooms)?
    ├─ Min-heap of end times     → LC 253
    └─ OR sweep line: split into +1 start / -1 end events

---

The Universal Overlap Check

Two intervals a = [s1, e1] and b = [s2, e2] overlap iff s1 <= e2 && s2 <= e1.

If intervals are sorted by start, the simpler check is: a.end >= b.start.

---

The Sort-and-Merge Template

Arrays.sort(intervals, (x, y) -> x[0] - y[0]);
List<int[]> merged = new ArrayList<>();
for (int[] cur : intervals) {
    if (merged.isEmpty() || merged.get(merged.size()-1)[1] < cur[0]) {
        merged.add(cur);                                  // disjoint → append
    } else {
        merged.get(merged.size()-1)[1] =
            Math.max(merged.get(merged.size()-1)[1], cur[1]);   // overlap → extend end
    }
}

The Meeting Rooms II Heap Template

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> endTimes = new PriorityQueue<>();   // min-heap of end times
for (int[] m : intervals) {
    if (!endTimes.isEmpty() && endTimes.peek() <= m[0]) endTimes.poll(); // reuse room
    endTimes.offer(m[1]);
}
return endTimes.size();

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Merge Intervals	56	Medium	Sort + merge
2	Insert Interval	57	Medium	3-phase scan
3	Non-overlapping Intervals	435	Medium	Greedy by end

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Meeting Rooms II	253	Medium	Min-heap of ends

---

Java Implementation Tips

• For sorting int[][], use lambda: Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
• Beware overflow in subtraction — use Integer.compare(a[0], b[0]) for large values.
• Final convert to array: merged.toArray(new int[merged.size()][]) (jagged 2-D array).
• For sweep line: build event list (time, +1 or -1), sort with ties — process end before start when times tie.

---

Senior Mental Trigger

“Intervals → sort first. Merge → by start. Greedy non-overlap → by end. Rooms count → heap of ends.”