How do you solve My Calendar II on LeetCode?

My Calendar II (LeetCode #731) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Understanding the concept of triple booking is crucial to solving this problem.

What is the brute force solution for My Calendar II?

The brute force approach for My Calendar II is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every existing booking to see if adding a new event would cause a triple booking. This is straightforward but inefficient as it requires checking all previous events for each new event. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for My Calendar II?

Always clarify the requirements and constraints of the problem before diving into coding. Think about edge cases, such as bookings that start or end at the same time. Practice explaining your thought process as you code; this helps interviewers understand your approach.

What are common mistakes when solving My Calendar II?

Not properly checking for overlaps before adding a new booking. Failing to update the double bookings list correctly.

#731

My Calendar II

Medium

ArrayBinary SearchDesignSegment TreePrefix SumOrdered SetHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

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

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses two lists to track single and double bookings. This allows us to efficiently check for overlaps and determine if a new booking can be added without causing a triple booking.

⚙️

Algorithm

3 steps

1Step 1: Maintain a list for single bookings and another for double bookings.
2Step 2: For each new booking, check against the double bookings to see if it overlaps.
3Step 3: If it does not overlap with any double booking, add it to the single bookings and update the double bookings accordingly.

solution.py14 lines

1class MyCalendarTwo:
2    def __init__(self):
3        self.single = []
4        self.double = []
5
6    def book(self, startTime: int, endTime: int) -> bool:
7        for s, e in self.double:
8            if startTime < e and s < endTime:
9                return False
10        for s, e in self.single:
11            if startTime < e and s < endTime:
12                self.double.append((max(startTime, s), min(endTime, e)))
13        self.single.append((startTime, endTime))
14        return True

ℹ

Complexity note: The time complexity is O(n) because we only iterate over the existing bookings to check for overlaps, making it efficient.

1Understanding the concept of triple booking is crucial to solving this problem.
2Using two lists to track single and double bookings allows for efficient checking of overlaps.

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