Intervals: Merge, Meeting Rooms and Calendar Booking

Learning Outcome

Choose sorting, heaps, sweep line, or ordered maps for interval conflict and range problems.

Pattern Recognition

Item	Detail
Core signal	The input is start/end ranges and the question asks merge, overlap, rooms, or dynamic booking.
Use when	Intervals can be compared by start/end or queried online by neighboring ranges.
Avoid when	The required invariant is not monotonic or the input constraints point to a simpler direct scan.

Intuition

Most interval decisions are local after sorting: only the previous merged end or earliest active end matters.

Exact Practice Question Names

Merge Intervals
Meeting Rooms
Meeting Rooms II
Meeting Rooms III
My Calendar I
Range Module

Interview Approach

Sort by start for merge and conflict checks.
Use a min-heap of end times for room counts.
Use sweep line for peak overlap.
Use ordered map/set lower_bound for online calendar/range modules.

Pseudocode

sort intervals by start
activeEnds = minHeap
for interval in intervals:
  while activeEnds.min <= interval.start: pop
  push interval.end
  answer = max(answer, heap size)

Sample Dry Run

For meetings [0,30],[5,10],[15,20], the heap reaches size 2 at time 5, then reuses one room before [15,20].

Edge Cases

end == start may not overlap
Unsorted input
Nested intervals
Online operations where sorting all input is impossible

Common Mistakes

Sorting by end for merge intervals
Treating touching intervals as overlap in meeting rooms
Not checking previous and next neighbor in calendar booking

Complexity

Item	Detail
Expected time	O(n log n) for sorting/heap variants; O(log n) per online ordered-map operation.
Expected space	O(n).

Java, C++ and Python Notes

Java: prefer explicit classes and clear helper methods over clever one-liners.
C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

Name the pattern before coding.
State the invariant or DP state in one sentence.
Dry-run the smallest non-trivial example.
Close with time and space complexity.