My Calendar III

Hard

Asked by:

6 views

Topics:

ArraysGreedy Algorithms

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

MyCalendarThree() Initializes the object.
int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

Constraints:

0 <= startTime < endTime <= 10⁹
At most 400 calls will be made to book.

Try coding it in LeetCode

My Calendar III

Hard

Asked by:

6 views

Topics:

ArraysGreedy Algorithms

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

MyCalendarThree() Initializes the object.
int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

Constraints:

0 <= startTime < endTime <= 10⁹
At most 400 calls will be made to book.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value for start and end times, and what is the acceptable range for their difference (i.e., the duration of an event)?
Can start and end times be equal, representing a zero-length event?
How should overlapping events with identical start and end times be handled? Are they considered distinct occurrences?
If multiple intervals overlap, do I need to return information about *which* intervals overlap, or just the maximum number of overlaps at any given time?
Is the `book` method expected to handle a large number of calls (potentially millions)? If so, are there any specific performance expectations beyond minimizing time complexity per `book` call (e.g., memory usage constraints)?

Brute Force Solution

Approach

The calendar problem wants us to find the maximum number of overlapping events. The brute force method simply checks every possible event overlap for each new event we add to the calendar. It's like trying every single possibility to see which one works.

Here's how the algorithm would work step-by-step:

Whenever we get a new event, compare it to every single event that's already in the calendar.
For each comparison, check if the new event overlaps with the existing event.
If they overlap, increase the overlap counter for that specific time period where the events intersect.
After comparing the new event with all existing events, find the highest overlap counter we found during all comparisons.
Store the new event in the calendar so it can be compared against future events.
Return the highest overlap counter we found as the maximum number of overlapping events.

Code Implementation

class MyCalendarThree:

    def __init__(self):
        self.calendar_events = []

    def book(self, start_time: int, end_time: int) -> int:
        self.calendar_events.append((start_time, end_time))
        maximum_overlapping_events = 0

        # Iterate through all events to find max overlaps
        for i in range(len(self.calendar_events)):
            current_overlap_count = 0
            event_one_start = self.calendar_events[i][0]
            event_one_end = self.calendar_events[i][1]

            # Compare current event with every other event
            for j in range(len(self.calendar_events)):
                if i == j:
                    current_overlap_count = max(current_overlap_count, 1)
                    continue

                event_two_start = self.calendar_events[j][0]
                event_two_end = self.calendar_events[j][1]

                # Check if two events overlap
                if event_one_start < event_two_end and event_two_start < event_one_end:
                    current_overlap_count += 1

            maximum_overlapping_events = max(maximum_overlapping_events, current_overlap_count)

        return maximum_overlapping_events

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through all existing events in the calendar for each new event being added. This means that for each of the 'n' events added over time, the algorithm compares it against all the other (potentially up to n) previously added events. These pair-wise comparisons for potential overlaps drive the computational cost. Therefore, the total number of comparisons grows proportionally to n * n/2, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm stores all events in the calendar for future comparisons. In the worst-case scenario, each event is unique and does not overlap with any other, so the calendar can grow linearly with the number of input events. Therefore, the space used by the calendar is proportional to N, where N is the number of events. This leads to a space complexity of O(N).

Optimal Solution

Approach

We want to efficiently track the maximum number of overlapping events at any given time. To do this, we focus on when events start and end, instead of checking every possible time point.

Here's how the algorithm would work step-by-step:

Keep track of when events start and end, associating a +1 with the start time and a -1 with the end time.
Sort all these start and end times together.
Go through the sorted times one by one. If you hit a start time (+1), increase a counter. If you hit an end time (-1), decrease the counter.
Keep track of the highest value the counter reaches. This will represent the maximum number of overlapping events.

Code Implementation

class MyCalendarThree:

    def __init__(self):
        self.timeline = {}

    def book(self, start_time: int, end_time: int) -> int:
        # Use +1 for start, -1 for end to track overlaps.
        self.timeline[start_time] = self.timeline.get(start_time, 0) + 1
        self.timeline[end_time] = self.timeline.get(end_time, 0) - 1

        sorted_times = sorted(self.timeline.keys())
        
        current_overlaps = 0
        max_overlaps = 0
        
        # Iterate through sorted times to maintain overlap count.
        for time_point in sorted_times:
            current_overlaps += self.timeline[time_point]

            # Update max overlaps seen so far.
            max_overlaps = max(max_overlaps, current_overlaps)

        return max_overlaps

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm's time complexity is dominated by two main operations. First, adding start and end times to a list will be O(n). Second, sorting the list of start and end times, which contains 2n elements, takes O(n log n) time using an efficient sorting algorithm like merge sort or quicksort. The final linear pass through the sorted list to count overlaps takes O(n) time. Therefore, the overall time complexity is O(n + n log n + n), which simplifies to O(n log n).

Space Complexity

O(N) – The solution stores event start and end times with associated +1 or -1 values. In the worst case, where all events are distinct and don't overlap at all, we would store 2N entries (N start times and N end times). These entries are stored in a list to be sorted. Thus, the auxiliary space used is proportional to the number of events, N, resulting in O(N) space complexity.

Edge Cases

Case	How to Handle
Empty input stream of events	The data structure should initialize and allow bookings even without initial events and return 0 as the maximum overlapping events.
Integer overflow of start or end times	Use appropriate data types (e.g., long) or modular arithmetic to prevent integer overflows when calculating overlaps.
Large number of events exceeding available memory	Consider using a segment tree or interval tree data structure that scales better with a large number of events, possibly offloading to disk.
Events with identical start and end times	Increment and decrement counters at the same index to correctly represent zero duration events, ensuring they don't improperly increase k.
Events that completely overlap other existing events	Increment the counter for the start of the completely overlapping event and decrement the counter for its end, adding to the existing overlap.
Events with very small durations or very large durations	The chosen data structure and algorithm should handle very small or very large durations without loss of precision or efficiency.
Overlapping events with identical start times	The data structure must correctly account for overlapping events at the same start time by incrementing the active count appropriately.
Consecutive bookings with near-identical start/end times causing floating-point precision issues if using floating-point	Use integers for start/end times, avoiding floating-point precision issues; if not possible, apply a small epsilon value when comparing times.