Leetcode 729. My Calendar I
Problem Description
The problem entails implementing a MyCalendar
class to store events. It should validate whether the new event will cause a double booking or not before adding it to the calendar. A double booking occurs when two events have some overlapping time.
The MyCalendar
class has a method book(int start, int end)
that represents a booking on the half-open interval [start, end), i.e., the range of real numbers x such that start
<= x < end
. When this method is called, it should return true
if the event can be added without causing a double booking and false
if otherwise.
Here is an example of how your class will be used:
1 2python 3cal = MyCalendar() 4cal.book(10, 20) # returns true 5cal.book(15, 25) # returns false because 15 to 20 is already booked 6cal.book(20, 30) # returns true because 20 is not inclusive in the first event.
Approach to the Solution
A naive solution to solve this problem is by using a list or an array. For each event we want to book, we can check every previously booked event for a conflict.
In the proposed solution, We use a list of pairs (sorted by their start time), where pair.first is the start of an event, and pair.second is the end of an event. For each event that we want to book, we look at all of the previous events and check if it conflicts. The event conflicts if its start time is less than the end of a previous event and its end time is greater than the start of the previous event.
Let's walkthrough an example:
- Let's assume we have an empty calendar and we want to book the event from 10 to 20:
1
2
3book(10,20)
After booking the above event, our calendar looks like this,
1 2 310 -------------------------- 20
- Now we want to book an event from 15 to 25:
1
2
3book(15,25)
As we see, there is a overlap with the previously booked event, so we return false and the calendar remains unchanged.
- Then we want to book an event from 20 to 30:
1
2
3book(20,30)
There is no overlap with the previously booked events, so we add this event and the calendar will look like this:
1 2 310 -------------------------- 20, 20 ---------------------------- 30
Python Solution
1 2python 3class MyCalendar: 4 5 def __init__(self): 6 self.timeline = [] 7 8 def book(self, start: int, end: int) -> bool: 9 # check if the given interval overlaps with any existing interval in the timeline 10 for s, e in self.timeline: 11 if start < e and end > s: # overlap condition 12 return False 13 # if no overlap, add the interval to the timeline 14 self.timeline.append((start, end)) 15 return True
Java Solution
1
2java
3import java.util.*;
4
5class MyCalendar {
6 List<int[]> calendar;
7
8 MyCalendar() {
9 calendar = new ArrayList<>();
10 }
11
12 public boolean book(int start, int end) {
13 for (int[] iv : calendar) {
14 if (iv[0] < end && start < iv[1]) return false; // overlap exists
15 }
16 calendar.add(new int[]{ start, end });
17 return true;
18 }
19}
Javascript Solution
1
2javascript
3class MyCalendar {
4 constructor() {
5 this.calendar = [];
6 }
7
8 book(start, end) {
9 for(let iv of this.calendar) {
10 if(iv[0] < end && start < iv[1]) return false; // overlap exists
11 }
12 this.calendar.push([start, end]);
13 return true;
14 }
15}
C++ Solution
1
2cpp
3class MyCalendar {
4 vector<pair<int, int>> calendar;
5public:
6 MyCalendar() {}
7
8 bool book(int start, int end) {
9 for(auto iv : calendar) {
10 if(iv.first < end && start < iv.second) return false; // overlap exists
11 }
12 calendar.push_back({ start, end });
13 return true;
14 }
15};
C# Solution
1
2csharp
3public class MyCalendar {
4 private List<KeyValuePair<int, int>> calendar;
5
6 public MyCalendar() {
7 calendar = new List<KeyValuePair<int, int>>();
8 }
9
10 public bool Book(int start, int end) {
11 foreach(var iv in calendar) {
12 if(iv.Key < end && start < iv.Value) return false; // overlap exists
13 }
14 calendar.Add(new KeyValuePair<int, int>(start, end));
15 return true;
16 }
17}
Solution Analysis
The primary advantage of the solution is its simplicity. It directly addresses the problem using a simple data structure and algorithm. The solution does not use a complex algorithm or data structure, thus making it quite straightforward to implement.
The time complexity is O(n) because, in the worst-case scenario, the book
function scans the entire list to determine if a given interval overlaps with any of the previously booked intervals. Here, 'n' is the number of previously booked intervals.
However, this solution is not optimal when it comes to scheduling a large number of events. If there are many events, then this solution can become slow. One potential improvement for handling large numbers of events would be to maintain the list of events in a sorted order, and then perform a binary search to find any overlapping event, which would reduce the time complexity to O(log n).
Final Words
This simple solution elegantly solves the problem of managing event booking on a calendar without overlaps. It is easily implementable in several programming languages including Python, Java, JavaScript, C++, and C#. However, if the number of events to be managed on the calendar is very large, it might become slow, and a more optimized approach is suggested in such cases.
While there is room for performance optimization, this solution provides a good starting point for understanding the problem and how to approach it. Readers are encouraged to improve upon this base solution by implementing more advanced data structures or algorithms.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.