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.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.
C++
Java
Python
C#
JavaScript
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.
Python
C++
Time Complexity: O(log N) for each booking due to TreeMap operations.
Space Complexity: O(N).
| 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. |
My Calendar I - Leetcode 729 - Python • NeetCodeIO • 14,889 views views
Watch 9 more video solutions →Practice My Calendar I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor