Lesson 5 of 8 · 48 min

Intervals and heaps

Merge/insert intervals, meeting rooms with heaps, top-K min-heap of size K, two-heap streaming median, and production scheduling/latency metaphors.

Sort key choice is the design decision

Interval problems look like geometry; they are really sort + sweep. Pick the wrong sort key and merge/meeting-rooms collapse. Heap problems look like “use a priority queue”; the real decision is min-heap of size K vs max-heap vs two heaps. Production: booking merge, top-K slowest endpoints, streaming p50. This lesson is the bridge from linear scans to structures that rebalance under inserts.
Intervals: represent as [start, end). Clarify inclusive/exclusive. Sort by start ascending (sometimes by end for scheduling). Merge: scan sorted, extend current end if overlap, else push and start new. Meeting Rooms II: sort starts and ends or use min-heap of end times — heap size is rooms in use. Insert Interval: one pass merge around the new interval.
Heaps: Python heapq is min-heap. Kth largest → min-heap of size K (root is answer). Top-K frequent → heap of size K on frequency. Streaming median → max-heap for lower half + min-heap for upper half; rebalance sizes. Always state O(log n) per insert and what the root represents.

Merge intervals

python
1MERGE INTERVALS — sort by start, extend or push23def merge(intervals: list[list[int]]) -> list[list[int]]:4    intervals.sort(key=lambda x: x[0])5    out: list[list[int]] = []6    for s, e in intervals:7        if not out or out[-1][1] < s:8            out.append([s, e])9        else:10            out[-1][1] = max(out[-1][1], e)11    return out1213# Overlap test: not (end < next_start). Touching ends: clarify if merge [1,2][2,3].14# O(n log n) sort dominates.
Clarify touching intervals: does [1,2] and [2,3] merge? Scheduling often yes. Production: merge availability windows before computing free slots for a meeting.

Meeting Rooms II — heap as active set

Given meeting [start,end], minimum rooms required. Sort by start. Min-heap stores end times of ongoing meetings. For each meeting, if heap root end ≤ start, pop (room frees). Push current end. Max heap size is answer. Alternative: separate start/end arrays, two pointers sweep — also fine; heap version narrates “active meetings” well.
python
1MEETING ROOMS II — min-heap of end times23import heapq45def min_meeting_rooms(intervals: list[list[int]]) -> int:6    if not intervals:7        return 08    intervals.sort(key=lambda x: x[0])9    ends: list[int] = []  # min-heap10    for s, e in intervals:11        if ends and ends[0] <= s:12            heapq.heappop(ends)13        heapq.heappush(ends, e)14    return len(ends)1516# Dry-run [[0,30],[5,10],[15,20]]: ends grow to 2 rooms.

Top-K with a bounded heap

python
1KTH LARGEST — min-heap of size k23import heapq45def find_kth_largest(nums: list[int], k: int) -> int:6    h: list[int] = []7    for x in nums:8        heapq.heappush(h, x)9        if len(h) > k:10            heapq.heappop(h)11    return h[0]1213# O(n log k) time, O(k) space. Quickselect average O(n) is follow-up.
Top-K slowest endpoints: feed (latency, endpoint) into min-heap of size K by latency, or max-heap of all if n is tiny. Interviewers want O(n log K) speech for large n.

Two-heap median sketch

Lower half in max-heap (invert signs in Python), upper half in min-heap. Invariant: sizes differ by at most 1; every in lower ≤ every in upper. Median is root of larger or average of roots. Production: streaming p50 without storing all samples (exact median needs the structure; approximate p50 uses t-digest later in career — mention only if asked).
python
1STREAMING MEDIAN — two heaps23import heapq45class MedianFinder:6    def __init__(self):7        self.lo: list[int] = []  # max-heap via negation8        self.hi: list[int] = []  # min-heap910    def add_num(self, num: int) -> None:11        heapq.heappush(self.lo, -num)12        heapq.heappush(self.hi, -heapq.heappop(self.lo))13        if len(self.hi) > len(self.lo):14            heapq.heappush(self.lo, -heapq.heappop(self.hi))1516    def find_median(self) -> float:17        if len(self.lo) > len(self.hi):18            return float(-self.lo[0])19        return (-self.lo[0] + self.hi[0]) / 2.0

Insert interval and sort-key traps

Insert Interval: one linear pass over already-sorted intervals — collect all fully left of new, merge all overlapping into new, append the rest. No full re-sort needed if input guaranteed sorted. If not sorted, sort first and say why. Interviewers ding candidates who re-sort a sorted list without comment (wasted O(n log n) narrative).
Greedy interval scheduling (max non-overlapping) sorts by end time, not start — different problem from merge. If you sort by the wrong key, you will still write clean code that fails hidden tests. Always restate: “merge cares about start order; max non-overlap cares about earliest finish.”
python
1INSERT INTERVAL — three-phase scan (input sorted by start)23def insert(intervals: list[list[int]], new: list[int]) -> list[list[int]]:4    res: list[list[int]] = []5    i, n = 0, len(intervals)6    # phase 1: completely to the left7    while i < n and intervals[i][1] < new[0]:8        res.append(intervals[i]); i += 19    # phase 2: merge overlap into new10    while i < n and intervals[i][0] <= new[1]:11        new[0] = min(new[0], intervals[i][0])12        new[1] = max(new[1], intervals[i][1])13        i += 114    res.append(new)15    # phase 3: rest16    while i < n:17        res.append(intervals[i]); i += 118    return res

Heap API fluency under pressure

In Python, max-heap is negation or tuples with negative priority — state that before buggy custom classes. For pairs (latency, endpoint), order ties deliberately (stable endpoint id) so behavior is deterministic. Pop/push costs O(log k); building a heap from n items is O(n) via heapify — mention if doing offline top-K.
Follow-up ladder interviewers use: (1) kth largest offline → heap or quickselect; (2) continuous stream → size-K heap; (3) median stream → two heaps; (4) delete-arbitrary → need ordered set / lazy deletion. Knowing where your solution sits on that ladder is senior Problem Solving even if you only implement step 2.

Interview prep

Interval/heap rounds are won by sort-key clarity and “what does the root mean?” sentences. Pre-answer these while drawing a tiny Gantt chart on paper.
  1. 01“Merge intervals steps?” → sort by start; extend end on overlap else push new.
  2. 02“Meeting rooms minimum?” → min-heap of ends; rooms = max heap size.
  3. 03“Why min-heap size K for kth largest?” → root is Kth; discard smaller than threshold.
  4. 04“Streaming median?” → max-heap lower + min-heap upper; rebalance sizes.
  5. 05“Sort key for intervals?” → usually start; end-sort for some greedy scheduling.
  6. 06“Touching intervals merge?” → clarify inclusive bounds with interviewer.
  7. 07“Complexity merge?” → O(n log n); heap ops O(log n) each.
  8. 08“Production?” → calendar merge; top-K latency; live p50 dashboard.
  9. 09"Merge intervals first step?" -> sort by start; linear merge ends.
  10. 10"Meeting rooms II?" -> min-heap of ends; pop if start >= earliest end.
  11. 11"Python max-heap?" -> heapq with negated values.
  12. 12"Streaming median?" -> max-heap lower + min-heap upper; rebalance sizes.
  13. 13"Non-overlapping greedy key?" -> sort by end time; take next with start >= last end.
  14. 14"K-way merge heap payload?" -> (value, list_id, index) to know which list to advance.
docsNeetCode — Merge IntervalsNeetCodearticleAlgoMaster — Heap / Top-K patternsAlgoMasterdocsPython heapq docsPython docsarticleTIH — heap / priority queueTech Interview Handbook

Interval sweep + heap templates with code

Intervals: merge (sort start, linear merge ends); insert (before/overlap/after); meeting rooms II (min-heap of ends or sort starts+ends); non-overlap greedy by end. Heaps: Kth largest size-k min-heap; top-K frequent; merge K lists; streaming median two heaps (full in L8); task scheduler max-heap + cooldown. Production: calendar merge, CI schedulers, MapReduce k-way merge, p50 trackers. Always sort intervals first — #1 live bug. heapq is min-heap; max-heap via negation. Always clarify whether endpoints are inclusive and whether touching intervals merge — [1,2] and [2,3] is a free Problem Solving point if you ask. For meeting rooms II, narrate: sort by start so time moves forward; min-heap of end times is the earliest free room; if next start >= that end, reuse, else open a room. Heap size is the answer. For K-way merge, push (value, list_id, index) so you know which list to advance. Practice sequence for a 45-minute mock: merge intervals (10 min) then meeting rooms II (15 min) then Kth largest (10 min) with four-axis self-score (10 min). On merge, force a dry-run of nested, touching, and disjoint cases. On rooms, draw the heap after each push/pop. On Kth largest, state why size-k min-heap beats full sort when k << n. If the interviewer asks for online insertion of intervals, you need an ordered map (TreeMap) or interval tree — say that as a follow-up even if you implement the offline sort version first.
python
1MERGE INTERVALS — sort + sweep23def merge(intervals: list[list[int]]) -> list[list[int]]:4    if not intervals:5        return []6    intervals = sorted(intervals, key=lambda x: x[0])7    out = [intervals[0][:]]8    for s, e in intervals[1:]:9        if s <= out[-1][1]:10            out[-1][1] = max(out[-1][1], e)11        else:12            out.append([s, e])13    return out  # O(n log n) + O(n)1415# Clarify touch semantics: does [1,2][2,3] merge? Ask before coding.16# Empty input and single interval are the first two dry-runs.
python
1MEETING ROOMS II — min-heap of end times23import heapq45def min_meeting_rooms(intervals: list[list[int]]) -> int:6    if not intervals:7        return 08    intervals = sorted(intervals, key=lambda x: x[0])9    ends: list[int] = []10    heapq.heappush(ends, intervals[0][1])11    for s, e in intervals[1:]:12        if s >= ends[0]:13            heapq.heappop(ends)14        heapq.heappush(ends, e)15    return len(ends)  # rooms in use = heap size1617# Alt: sort starts and ends separately; two pointers count concurrent.
Graders + tiers. "Sort by start, sweep, heap of ends." Greedy end-time for non-overlap vs rooms-count. Inclusive end off-by-ones. Clarify touch. FAANG: merge + rooms + heap follow-ups. India OA: merge staple. AI lab: scheduler under SLO constraints. Streaming median is the bridge to L8 capstone — if two-heap rebalance is shaky, fix it before the mock week. Keep TIH interval + heap cheatsheets and Abdul Bari heap fundamentals open for intuition, then implement without looking. Add LC 253 Meeting Rooms II (or the free-description variant), LC 215 Kth Largest, and LC 23 Merge K Lists to a single timed set. After each, write one sentence on which axis was weakest — that failure log beats another random medium. When you can merge intervals and open rooms while narrating complexity without looking at notes, move on; until then, this lesson is not done. Touch-endpoint clarification alone has saved more hire packets than clever heap tricks.
Merge Intervals — NeetCodeNeetCodearticleInterval cheatsheet — TIHTech Interview HandbookarticleHeap problems guide — LeetCode discussLeetCode Discuss

Checkpoint

Meetings: [0,10], [10,20]. Do you need 1 room or 2 if ends are exclusive-start-ok?

AAlways 2 — any shared boundary needs two roomsBClarify bound policy; with ends[0] <= start free room (common LC rule) → 1 roomCImpossible to know without segment tree
Sign up free to answer and see why

Checkpoint

Why min-heap of size K for Kth largest rather than max-heap of size n?

AMin-heap is always faster for all problemsBYou only need the K largest boundary; root of size-K min-heap is the Kth; O(n log K) vs O(n log n) full sortCMax-heap cannot find large elements
Sign up free to answer and see why

Checkpoint

Merge intervals failed tests: sorted by end ascending instead of start. Likely symptom?

AStill always correct because sort is optionalBMissed merges / wrong order — linear scan assumes nondecreasing startsCOnly performance regression
Sign up free to answer and see why

Checkpoint

Streaming median: lower max-heap has 3 elems, upper min-heap has 1 after a bug. Fix?

AClear both heaps and re-insert all history onlyBRebalance: move roots until sizes differ by at most 1 and max(lower)≤min(upper)CAlways trust find_median without size checks
Sign up free to answer and see why

Checkpoint

Production: top 5 slowest endpoints in a 10M-event stream. Best default?

ASort all 10M latencies each queryBMin-heap of size 5 keyed by latency (or continuous top-K structure); O(n log 5) per full passCStore only average latency map and ignore heap
Sign up free to answer and see why

Can you implement merge intervals and meeting rooms II with heap narration, plus explain size-K min-heap for kth largest?

New to itGetting thereConfident

Takeaways

  • Intervals: sort key + linear merge/sweep.
  • Meeting rooms: min-heap of end times = active set.
  • Top-K: min-heap size K; know O(n log K).
  • Streaming median: two heaps + size invariant.
  • Clarify touching interval bounds early.

Next: modified binary search — rotated arrays, first/last, and search-on-answer capacity problems.

Sources

Free to read · better with Enzo

Learn it with Enzo

Save your progress, answer the checkpoints, and let Enzo quiz you on what you just read.

Continue with EnzoSign up free