Interval day — Merge Intervals, Insert Interval, and Meeting Rooms II with its whole follow-up tree. Quick notes:
- Sorting by start is the move that turns "overlap could be anywhere" into "overlap only with my neighbor" — that's the entire foundation of Merge Intervals
- The invariant worth saying out loud: the merged list stays disjoint and sorted, so the last interval's end is always the biggest end seen — and that's exactly why
max(lastEnd, end)matters for contained intervals like[1,10],[2,3] - Insert Interval can be written to mirror Merge Intervals' shape: carry the new interval through a single pass, absorb overlaps with min/max (it grows in BOTH directions), and don't forget the final append when nothing comes after it
- Meeting Rooms II in one sentence: overlapping meetings don't merge — they scatter into separate rooms, so I'm tracking MANY end times, and the only one I ever need to check is the smallest → min-heap
- The min-heap logic is pure common sense: if even the earliest-ending room isn't free, no room is
- Follow-up "no heap?": since the answer is just a count, split intervals into +1 start events and -1 end events, sort each, sweep with two pointers, track the peak
- Follow-up "which room does each meeting get?": heap entries become (end, roomId) pairs — tuples compare by first element, so the heap still ranks by end time, but now identity survives. The two-pointer version threw identity away and can't answer this
- Follow-up "times are small and bounded?": skip sorting — a bucket array (difference array). One slot per minute, +1/-1 stickers, one left-to-right walk. Same trick as counting sort: use the value as the index and ordering is free. O(n + range)
- Follow-up "streaming bookings?": the sort assumption breaks → switch to a structure that keeps itself sorted (balanced BST / segment tree) — that's the My Calendar series
- The question that organizes this whole family: do I need identities, or just counts? Counts → sweep/bucket. Identities → heap with ids