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.
This approach uses a simple list to store existing bookings. For each new booking, we check against all previously booked intervals to ensure there is no overlap. If an overlap is found, the booking is denied; otherwise, it's added to the list. Although straightforward, this approach can be inefficient for many bookings, as each booking incurs a linear scan through the list of existing bookings.
This C program maintains a two-dimensional array 'booked' which stores the start and end of each booking. The 'book' function iterates through existing bookings and checks for overlap. If no overlap is found, it adds the new booking.
Time Complexity: O(N) for each booking, where N is the number of existing bookings.
Space Complexity: O(N) for storing the bookings.
This approach leverages a data structure like a TreeMap (Java) or SortedDict (Python) to efficiently manage and query intervals. These structures allow us to quickly find the nearest existing intervals to check for overlaps, enabling faster insert operations compared to a simple list. By maintaining the intervals in a sorted order, we can reduce the number of overlaps checks necessary for each new booking.
In this Java solution, a TreeMap is used to maintain ordered bookings. 'floorKey' and 'ceilingKey' efficiently find adjacent bookings to check for overlaps with the new booking's start and end times.
Time Complexity: O(log N) for each booking due to TreeMap operations.
Space Complexity: O(N).
We can use an ordered set to store the schedule. An ordered set can perform insert, delete, and search operations in O(log n) time. The elements in the ordered set are sorted by the endTime of the schedule in ascending order.
When calling the book(start, end) method, we search for the first schedule in the ordered set with an end time greater than start. If it exists and its start time is less than end, it means there is a double booking, and we return false. Otherwise, we insert end as the key and start as the value into the ordered set and return true.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of schedules.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force with List | Time Complexity: O(N) for each booking, where N is the number of existing bookings. |
| Approach 2: Balanced Tree Using TreeMap | Time Complexity: O(log N) for each booking due to TreeMap operations. |
| Ordered Set | — |
| 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 |
My Calendar I - Leetcode 729 - Python • NeetCodeIO • 18,468 views views
Watch 9 more video solutions →Practice My Calendar I with our built-in code editor and test cases.
Practice on FleetCode