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:

1. 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

2. 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.

3. 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.