My Calendar II

My Calendar II

What is this problem about?

The My Calendar II problem extends the booking problem to allow up to one overlap (double-booking) but no triple-booking. The book(start, end) returns true if adding the event doesn't cause any time slot to be covered three or more times, and false otherwise. This My Calendar II coding problem tests two-level interval tracking.

Why is this asked in interviews?

Uber, Amazon, and Google ask this as a direct extension of My Calendar I. It tests whether candidates can extend their interval tracking to handle "at most k overlaps" — a generalization pattern. The array, design, binary search, ordered set, segment tree, and prefix sum interview pattern is applied here with two levels of overlap tracking.

Algorithmic pattern used

Two sorted lists: booked (all confirmed events) and overlaps (regions where exactly one overlap exists). For book(start, end):

1. Check if [start, end) overlaps with any interval in overlaps. If yes, return false (would cause triple-booking).
2. Compute the intersections of [start, end) with each interval in booked. Add these intersections to overlaps.
3. Add [start, end) to booked. Return true.

Example explanation

Book (10, 20): booked=[(10,20)], overlaps=[]. Return true. Book (15, 25): intersect with (10,20)→(15,20). overlaps=[(15,20)]. booked=[(10,20),(15,25)]. Return true. Book (20, 30): check overlaps (15,20). 20 ≥ 20 → no overlap with overlaps. Add to booked. Return true. Book (17, 22): check overlaps. (17,22) overlaps (15,20)? 17<20 AND 15<22 → overlap! Return false.

Common mistakes candidates make

• Checking for overlap with booked list instead of overlaps list first.
• Not computing the intersection correctly when adding to overlaps.
• Using O(n²) brute force when a smarter approach exists.
• Confusing "double booking" with "triple booking."

Interview preparation tip

My Calendar II introduces the concept of "tracking overlaps at each level." The pattern generalizes: maintain a list for each booking level. Checking the highest-level list first prevents the next booking level. After mastering I and II, the difference map approach (segment tree or sorted difference array) handles arbitrary k levels efficiently — a key technique for My Calendar III. Practice the two-list approach here until it's fluent.