We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

My Calendar III

Number: 732

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Design and implement a calendar system that supports booking events in a way that efficiently tracks the maximum number of simultaneous events (i.e. the maximum k-booking). Each time an event is booked with a start time and an end time, return the current maximum number of overlapping events.

Key Insights

  • Use a sweep-line or difference array method where each booking updates a counter at the start time and decrements it at the end time.
  • Sorting the “time points” and iterating through them allows computation of the current overlap count.
  • Although a segment tree can be used for scalability, given the constraints (at most 400 bookings), a map-based sweep-line approach is efficient and simple.
  • The challenge lies in efficiently tracking and updating these overlapping intervals without reprocessing the complete list of events each time.

Space and Time Complexity

Time Complexity: O(N log N) per booking call, where N is the number of distinct time points (worst-case 2 * number of bookings). Space Complexity: O(N) to store the timeline difference mapping.

Solution

The solution uses a map (or TreeMap in Java, sorted map in C++) to maintain a difference counter at each unique time. For each booking, increment the counter at the start time and decrement it at the end time. Then, iterate through the sorted keys of the map, summing the differences to compute current overlap, and update the maximum seen count. This technique is commonly referred to as a "sweep line" algorithm.

Code Solutions

# Python implementation of MyCalendarThree.
class MyCalendarThree:
    def __init__(self):
        # Initialize a dictionary to record the difference array.
        self.timeline = {}

    def book(self, startTime: int, endTime: int) -> int:
        # Add the event: increment at start time.
        self.timeline[startTime] = self.timeline.get(startTime, 0) + 1
        # Decrement at end time since the event finishes before endTime.
        self.timeline[endTime] = self.timeline.get(endTime, 0) - 1
        
        current = 0
        max_booking = 0
        # Iterate over the timeline in sorted order to compute overlaps.
        for time in sorted(self.timeline.keys()):
            current += self.timeline[time]
            max_booking = max(max_booking, current)
        return max_booking
← Back to All Questions