729. My Calendar I

MediumDesignSegment TreeBinary SearchOrdered Set

Problem Description

In this problem, you are tasked with creating a program that acts as a calendar. The primary function of this calendar is to ensure that when a new event is added, it doesn't clash with any existing events (a situation referred to as a "double booking"). An event is defined by a start time and an end time, which are represented by a pair of integers. These times create a half-open interval [start, end), meaning it includes the start time up to, but not including, the end time.

Your job is to implement a MyCalendar class that will hold the events and has the following capabilities:

MyCalendar() is a constructor that initializes the calendar object.
book(int start, int end) is a method that adds an event to the calendar if it does not conflict with any existing events. If the event can be added without causing a double booking, it returns true; otherwise, it returns false and does not add the event.

The goal is to ensure that no two events overlap in time.

Intuition

The key to solving this problem is to efficiently determine whether the newly requested booking overlaps with any existing bookings. One way to approach this is by maintaining a sorted list of events, allowing for quick searches and insertions.

The intuition is to search for the correct location to insert a new event such that the list remains sorted. We must check two things:

That the new event's start time does not conflict with the end time of the previous event.
That the new event's end time does not conflict with the start time of the next event.

We can accomplish this by:

Using the sortedcontainers.SortedDict class, which keeps keys in a sorted order. This allows us to quickly find the position where the new event could be inserted.
Applying the bisect_right method to find the index of the smallest event end that is greater than the new event's start time.
Checking if the new event's end time conflicts with the next event's start time in the sorted dictionary.
If there is no conflict, we insert the new event into the "sorted" dictionary, with the end time as the key and the start time as the value.
By keeping the dictionary sorted by the end time, this ensures that we can always quickly check for potential overlap with the immediately adjacent events in the sorted list of bookings.

The implementation of the book method in our solution proceeds with this intuition, allowing for efficient booking operations. Each booking can be processed in logarithmic time with respect to the number of existing bookings, therefore making the solution scalable for a large number of events.

Learn more about Segment Tree and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Solution Approach

The implementation of MyCalendar relies on the sortedcontainers Python library, which offers a SortedDict data structure to maintain the events sorted by their end times. Here's a walkthrough of how the solution is implemented using this SortedDict:

Initialization: When the MyCalendar class is instantiated, it initializes a SortedDict in the constructor. This SortedDict is stored in the self.sd attribute of the class instances, ready to keep track of the booked events.
```
1def __init__(self):
2    self.sd = SortedDict()
```

Booking an Event: The book method is where the logic to check for double bookings and add events takes place.

First, we find the index (position) where the new event's end time would be inserted into the SortedDict. We use the bisect_right method, which returns an index pointing to the first element in the SortedDict's values that is greater than the start time.
```
1idx = self.sd.bisect_right(start)
```
Now, we need to ensure that the new event does not conflict with the next event in the SortedDict. We check if the found index is within the bounds of the SortedDict and if the new event's end time is greater than the start time of the event at that index.
```
1if idx < len(self.sd) and end > self.sd.values()[idx]:
2    return False
```
If there is no conflict, it means the new event does not cause a double booking, and we insert it into the dictionary. Here, the event's end time is used as the key and the start time as the value. This ensures the events are sorted by their end times.
```
1self.sd[end] = start
```
After successfully adding the event without conflicts, the method returns True.
If at any point we detect an overlap (a potential double booking), we return False without adding the event.

1def book(self, start: int, end: int) -> bool:
2    idx = self.sd.bisect_right(start)
3    if idx < len(self.sd) and end > self.sd.values()[idx]:
4        return False
5    self.sd[end] = start
6    return True

The book method performs at most two key operations: finding where to insert and actually inserting the event. Both operations are efficient due to the nature of the SortedDict, which maintains the order of keys and allows for binary search insertions and lookups. This is how the provided solution ensures no double bookings occur while adding events to the MyCalendar.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's go through a small example to illustrate the solution approach.

Imagine we have a MyCalendar instance and we want to book two events. The first event is from time 10 to 20, and the second event is from time 15 to 25.

When we try to book the first event:

We initialize our MyCalendar and its underlying SortedDict, currently empty.
We attempt to book an event with start=10 and end=20.
self.sd.bisect_right(10) will return 0 since there are no keys greater than 10 (as the dictionary is empty).
Since the index 0 is within bounds and there are no events, there are no conflicts.
We add the event to the SortedDict with key 20 and value 10.

Now, MyCalendar looks like this:

self.sd contains {20: 10}

When we try to book the second event:

We attempt to book the second event with start=15 and end=25.
self.sd.bisect_right(15) will return index 0 since 20 is the first key greater than 15.
We check if idx is within bounds and if end (25) is greater than the start time of the event at index 0 (which is 10). Since 25 is indeed greater than 10, there is a potential overlap with the existing event.
Since end time 25 of the new event is greater than start time 10 of the existing event, which would result in a double booking, we return False.

Thus, the attempt to book an event from time 15 to 25 fails, preserving the non-overlapping constraint of the calendar. The SortedDict remains unchanged with the single event {20: 10} and no double booking occurs.

Solution Implementation

1from sortedcontainers import SortedDict
2
3class MyCalendar:
4    def __init__(self):
5        # Create a sorted dictionary to store the end time of each event
6        # as the key and the start time as the value
7        self.sorted_events = SortedDict()
8
9    def book(self, start: int, end: int) -> bool:
10        """
11        Attempts to book an event in the calendar based on the provided start and end times.
12        Returns True if the event can be booked (doesn't overlap with existing events);
13        otherwise returns False.
14
15        :param start: The start time of the event
16        :param end: The end time of the event
17        :return: Boolean indicating whether the event was successfully booked
18        """
19        # Find the index of the first event that ends after the requested start time
20        next_event_index = self.sorted_events.bisect_right(start)
21      
22        # Check if there is a conflict with the next event:
23        # - If next_event_index is within the bounds of the sorted dictionary,
24        #   check if the requested end time is greater than the start time of the next event.
25        if next_event_index < len(self.sorted_events) and end > self.sorted_events.values()[next_event_index]:
26            return False  # Event cannot be booked due to overlap
27      
28        # If there is no conflict, insert the new event into the sorted dictionary.
29        self.sorted_events[end] = start
30        return True  # Event booked successfully
31
32# Example of how to instantiate the MyCalendar class and book events:
33# calendar = MyCalendar()
34# is_booked = calendar.book(start, end)
35# print(is_booked)
36

1import java.util.Map;
2import java.util.TreeMap;
3
4// The class MyCalendar is designed to store bookings as intervals.
5// It uses a TreeMap to keep the intervals sorted by start time.
6class MyCalendar {
7
8    // Using TreeMap to maintain the intervals sorted by the start key.
9    private final TreeMap<Integer, Integer> calendar;
10
11    // Constructor initializes the TreeMap.
12    public MyCalendar() {
13        calendar = new TreeMap<>();
14    }
15
16    /**
17     * Tries to book an interval from start to end.
18     * @param start the starting time of the interval
19     * @param end the ending time of the interval
20     * @return true if the booking does not conflict with existing bookings, false otherwise
21     */
22    public boolean book(int start, int end) {
23        // Retrieves the maximum entry whose key is less than or equal to start.
24        Map.Entry<Integer, Integer> floorEntry = calendar.floorEntry(start);
25      
26        // If there is an overlap with the previous interval, return false.
27        if (floorEntry != null && floorEntry.getValue() > start) {
28            return false;
29        }
30      
31        // Retrieves the minimum entry whose key is greater than or equal to start.
32        Map.Entry<Integer, Integer> ceilingEntry = calendar.ceilingEntry(start);
33      
34        // If there is an overlap with the next interval, return false.
35        if (ceilingEntry != null && ceilingEntry.getKey() < end) {
36            return false;
37        }
38      
39        // If there is no overlap, add the interval to the TreeMap and return true.
40        calendar.put(start, end);
41        return true;
42    }
43}
44
45// Usage example:
46// MyCalendar obj = new MyCalendar();
47// boolean isBooked = obj.book(start, end);
48

1#include <map>
2using namespace std;
3
4class MyCalendar {
5private:
6    // map to keep track of event starts (+1) and ends (-1)
7    map<int, int> events;
8
9public:
10    // Constructor initializes the MyCalendar object
11    MyCalendar() {
12    }
13
14    /* Function to book a new event from 'start' to 'end' time.
15       Returns true if the event can be booked without conflicts, 
16       otherwise returns false. */
17    bool book(int start, int end) {
18        // Increment the count for the start time of the new event
19        events[start]++;
20        // Decrement the count for the end time of the new event
21        events[end]--;
22
23        int currentEvents = 0; // counter for overlapping events
24
25        // Iterate through all time points in the map
26        for (auto& keyValue : events) {
27            // Add up the values to check for overlaps
28            currentEvents += keyValue.second;
29          
30            // If more than one event is happening at the same time, revert changes and return false
31            if (currentEvents > 1) {
32                events[start]--;
33                events[end]++;
34                return false;
35            }
36        }
37      
38        // No overlap found, event is successfully booked
39        return true;
40    }
41};
42
43// Example usage:
44// MyCalendar* calendar = new MyCalendar();
45// bool canBook = calendar->book(start,end);
46

1// A global array to keep track of booked time slots as an array of start-end pairs.
2let calendar: number[][] = [];
3
4/**
5 * Attempts to book a new event in the calendar.
6 *
7 * @param {number} start The start time of the event.
8 * @param {number} end The end time of the event.
9 * @return {boolean} True if the event can be successfully booked without conflicts; otherwise, false.
10 */
11function book(start: number, end: number): boolean {
12    // Iterate through each already booked event in the calendar.
13    for (const item of calendar) {
14        // If the new event overlaps with an existing event, return false.
15        if (end > item[0] && start < item[1]) {
16            return false;
17        }
18    }
19    // If there is no overlap, add the new event to the calendar and return true.
20    calendar.push([start, end]);
21    return true;
22}
23

Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

O(1)O(log n)O(n)O(n logn)

I don’t know

Time and Space Complexity

The provided code implements a class MyCalendar that stores the start time of the events as values and the end time as keys in a SortedDict. When a new event is booked, it checks if there is any overlap with existing events and then stores the event in the SortedDict if there is no overlap.

Time Complexity

__init__: The constructor simply creates a new SortedDict, which is an operation taking O(1) time.
book: This method involves two main actions. First, it performs a binary search to find the right position where the new event should be inserted. The bisect_right method in SortedDict runs in O(log n) time where n is the number of keys in the dictionary. Secondly, the code inserts the new (end, start) pair into the dictionary. Inserting into a SortedDict also takes O(log n) time. Therefore, the overall time complexity for each book operation is O(log n).

Space Complexity

The space complexity of the code is mainly dictated by the storage requirements of the SortedDict.

With no events booked, the space complexity is O(1) as only an empty SortedDict is maintained.
As events are added, the space complexity grows linearly with the number of non-overlapping events stored. Therefore, in the worst-case scenario, where the calendar has n non-overlapping events, the space complexity would be O(n).

Overall, the space complexity of the MyCalendar data structure is O(n) where n is the number of non-overlapping events booked in the calendar.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

729. My Calendar I

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings