My Calendar III

Hard · Intervals · about 25 minutes

Asked at Google, Amazon, Microsoft.

A k-booking happens when k events share some moment. Events are half-open intervals [start, end).

• MyCalendarThree() creates an empty calendar.
• book(start, end) adds the event (always accepted) and returns the largest k such that a k-booking exists

in the calendar.

Related guides

• Segment & Fenwick Trees
• Intervals