How do you solve My Calendar III on LeetCode?

My Calendar III (LeetCode #732) 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: Each booking can be represented as two events: a start and an end.

What is the brute force solution for My Calendar III?

The brute force approach for My Calendar III is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each event against all previously booked events to count overlaps. This is straightforward but inefficient, especially as the number of events grows. The optimal Optimal Solution approach improves this to O(n log n).

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

My Calendar III uses the following concepts: Binary Search, Design, Segment Tree, Prefix Sum, Ordered Set. The recommended patterns to study are: Sweep Line, Sorting, Event Counting.

What are the interview tips for My Calendar III?

Explain your thought process clearly while coding. Consider edge cases, such as bookings that start and end at the same time. Discuss the trade-offs of different approaches before diving into code.

What are common mistakes when solving My Calendar III?

Not considering the end time correctly when counting overlaps. Forgetting to sort the events before processing.

#732

My Calendar III

Hard

Binary SearchDesignSegment TreePrefix SumOrdered SetSweep LineSortingEvent Counting

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)

The optimal solution uses a sweep line algorithm where we treat each booking as two events: a start and an end. By sorting these events and counting overlaps, we can efficiently determine the maximum number of overlapping bookings.

⚙️

Algorithm

3 steps

1Step 1: Create an array of events, where each booking contributes a start and an end event.
2Step 2: Sort the events first by time, and then by type (start before end if they are the same time).
3Step 3: Traverse the sorted events, maintaining a count of active bookings and updating the maximum count.

solution.py14 lines

1class MyCalendarThree:
2    def __init__(self):
3        self.events = []
4
5    def book(self, startTime: int, endTime: int) -> int:
6        self.events.append((startTime, 1))  # Start event
7        self.events.append((endTime, -1))    # End event
8        self.events.sort()  # Sort events
9        max_k = 0
10        current_k = 0
11        for time, count in self.events:
12            current_k += count
13            max_k = max(max_k, current_k)
14        return max_k

ℹ

Complexity note: The time complexity is dominated by the sort operation, which is O(n log n). The space complexity is O(n) due to storing the events.

1Each booking can be represented as two events: a start and an end.
2Sorting events allows us to efficiently count overlaps in a single pass.

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