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.In #729 My Calendar I, you need to design a calendar system that allows booking time intervals as long as they do not overlap with existing events. The key challenge is efficiently checking whether a new interval conflicts with previously booked ones.
A common approach is to store intervals in a sorted structure such as an ordered set or balanced binary search tree. By keeping events sorted by their start time, you can quickly locate the nearest events before and after the proposed booking. If the new interval does not overlap with these neighbors, the booking can be safely inserted.
Another approach uses a sorted array with binary search to find the correct insertion point. After locating the position, only adjacent intervals need to be checked for conflicts. This reduces unnecessary comparisons and keeps the structure ordered.
These strategies focus on efficient interval management, typically achieving O(log n) lookup time with ordered structures while maintaining minimal additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Ordered Set / Balanced BST | O(log n) per booking | O(n) |
| Sorted Array with Binary Search | O(log n) search + O(n) insertion | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Store the events as a sorted list of intervals. If none of the events conflict, then the new event can be added.
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.
Time Complexity: O(N) for each booking, where N is the number of existing bookings.
Space Complexity: O(N) for storing the bookings.
1#include <stdbool.h>
2#include <stdio.h>
3
4#define MAX_EVENTS 1000
5
6int booked[MAX_EVENTS][
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.
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.
Time Complexity: O(log N) for each booking due to TreeMap operations.
Space Complexity: O(N).
1import java.util.TreeMap;
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, interval scheduling and calendar booking problems are common in technical interviews at companies like Google, Amazon, and Meta. They test knowledge of data structures, interval logic, and efficient search techniques.
An ordered map or balanced binary search tree is typically the best choice. It keeps intervals sorted by start time and allows fast lookups of adjacent intervals, making overlap checks efficient.
The optimal approach is to store intervals in a balanced ordered structure such as a TreeMap or ordered set. This allows you to quickly find neighboring intervals and check for overlaps in O(log n) time. It ensures efficient booking even as the number of events grows.
Yes, you can maintain a sorted list of intervals and use binary search to locate the insertion point for a new booking. After finding the position, you only need to check the immediate neighbors for overlaps.
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.