How do you solve My Calendar I on LeetCode?

My Calendar I (LeetCode #729) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Using binary search can significantly reduce the time complexity of checking for overlaps.

What is the brute force solution for My Calendar I?

The brute force approach for My Calendar I is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each existing booking to see if the new booking overlaps with any of them. If it does, we cannot add the booking; otherwise, we can. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve My Calendar I?

My Calendar I uses the following concepts: Array, Binary Search, Design, Segment Tree, Ordered Set. The recommended patterns to study are: Binary Search, Array.

What are the interview tips for My Calendar I?

Always clarify the problem constraints and edge cases before jumping to coding. Explain your thought process clearly while coding to demonstrate your understanding. Consider both time and space complexity when discussing your solution.

What are common mistakes when solving My Calendar I?

Not considering the half-open interval correctly, leading to incorrect overlap checks. Failing to handle edge cases where bookings are exactly at the boundaries.

#729

My Calendar I

Medium

ArrayBinary SearchDesignSegment TreeOrdered SetBinary SearchArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

By storing the bookings in a sorted list, we can use binary search to efficiently find the position where the new booking would fit, allowing us to check for overlaps quickly.

⚙️

Algorithm

3 steps

1Step 1: Initialize an empty list to store booked events.
2Step 2: For each new booking request, use binary search to find the correct position to insert the new booking.
3Step 3: Check the adjacent bookings to see if there is an overlap. If there is no overlap, insert the new booking and return true; otherwise, return false.

solution.py14 lines

1import bisect
2
3class MyCalendar:
4    def __init__(self):
5        self.bookings = []
6
7    def book(self, startTime: int, endTime: int) -> bool:
8        i = bisect.bisect_left(self.bookings, (startTime, endTime))
9        if i > 0 and self.bookings[i - 1][1] > startTime:
10            return False
11        if i < len(self.bookings) and self.bookings[i][0] < endTime:
12            return False
13        self.bookings.insert(i, (startTime, endTime))
14        return True

ℹ

Complexity note: The time complexity is O(n log n) due to the binary search for insertion, while space complexity is O(n) for storing the bookings.

1Using binary search can significantly reduce the time complexity of checking for overlaps.
2Storing intervals in a sorted manner allows for efficient insertion and overlap checking.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.