Watch 10 video solutions for My Calendar I, a medium level problem involving Array, Binary Search, Design. This walkthrough by NeetCodeIO has 18,468 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.
A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).
The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendar class:
MyCalendar() Initializes the calendar object.boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.
Example 1:
Input ["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]] Output [null, true, false, true] Explanation MyCalendar myCalendar = new MyCalendar(); myCalendar.book(10, 20); // return True myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event. myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.
Constraints:
0 <= start < end <= 1091000 calls will be made to book.Problem Overview: Design a calendar system that supports booking events represented as halfβopen intervals [start, end). A booking should only succeed if the new event does not overlap with any existing event. The task is to efficiently detect interval conflicts while storing previously accepted bookings.
Approach 1: Brute Force with List (Time: O(n) per booking, Space: O(n))
Store all accepted bookings in a simple list of intervals. When a new booking request arrives, iterate through every stored interval and check for overlap. Two intervals overlap if start < existingEnd and end > existingStart. If any overlap is found, reject the booking; otherwise append the interval to the list. This approach relies only on basic array-style storage and linear scanning. It works well for small input sizes and is easy to implement during an interview, but performance degrades as the number of bookings grows because every operation scans the entire list.
Approach 2: Balanced Tree Using TreeMap (Time: O(log n) per booking, Space: O(n))
A more scalable solution keeps bookings sorted by start time using a balanced search tree such as TreeMap in Java or an ordered structure in C++/Python. Each key represents the start time and the value stores the end time. When inserting a new interval, you only need to check the immediate neighbors in sorted order. Use a floor search to find the previous interval and verify that its end does not exceed the new start. Then use a ceiling search to ensure the next interval does not begin before the new end. Because the structure maintains sorted order internally, each lookup and insertion runs in O(log n). This approach leverages concepts from binary search and ordered set data structures.
Some advanced implementations also model the calendar with a segment tree to support more complex booking queries, but for the constraints of My Calendar I that level of structure is unnecessary.
Recommended for interviews: The balanced tree approach is what most interviewers expect. It shows you understand ordered data structures and how to check only adjacent intervals instead of scanning the entire dataset. Starting with the brute force solution demonstrates correctness and reasoning, while optimizing to O(log n) using a tree structure demonstrates algorithmic maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with List | O(n) per booking | O(n) | Simple implementation or small number of bookings |
| Balanced Tree (TreeMap / Ordered Map) | O(log n) per booking | O(n) | Large number of bookings where efficient neighbor lookup is required |