Intervals

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   An interval is [start, end]. Sort first (by start to merge or sweep, by end to keep the most), then one pass decides each interval once.

   #1
2. ↯use it when

   "Merge", "insert", "overlap", "rooms needed", "free time", "remove the fewest so none overlap", "capacity along a route".

   #2
3. { }template

   Sort by start; if cur[0] > last[1] open a new group, else last[1] = Math.max(last[1], cur[1]).

   #3
4. { }template

   Rooms: min-heap of ends. if (!pq.isEmpty() && pq.peek() <= s) pq.poll(); pq.offer(e); The heap's size is the answer.

   #4
5. O( )cost

   O(n log n) for the sort, O(n) for the sweep, O(log n) per heap step. A difference array is O(n + range).

   #5
6. !trap

   Touching rules differ: [1,4]+[4,5] merge in LC 56, but [1,2] and [2,3] live together in LC 435 and meeting rooms. One < vs <=.

   #6
7. !trap

   (a, b) -> a[1] - b[1] overflows near ±2³¹ and silently mis-sorts (LC 452). Use Integer.compare.

   #7
8. !trap

   Merging with last[1] = cur[1] shrinks the group on nested intervals like [1,10], [2,3]. Always take the max.

   #8
9. ✦pro tip

   Draw the intervals as bars on a number line first. The sort key and the overlap rule jump out.

   #9

Shaky on a card? Open the chapter or flip its recall cards.