algoadvance

Leetcode 731. My Calendar II

Problem Statement:

Implement a MyCalendarTwo class to manage calendar booking requests.

You are to implement a data structure that can handle booking requests such that:

• If the requested event can be added without causing a triple booking (i.e., three events overlapping), the event is added successfully.
• Otherwise, the requested event is not added.

Your class should support the following two operations:

1. MyCalendarTwo(): Initializes the calendar object.
2. bool book(int start, int end): Attempts to book an event from start to end (exclusive). If adding this event does not cause a triple booking, it returns true; otherwise, it returns false.

Example:

MyCalendarTwo* obj = new MyCalendarTwo();
bool param_1 = obj->book(10, 20); // Returns true
bool param_2 = obj->book(50, 60); // Returns true
bool param_3 = obj->book(10, 40); // Returns true
bool param_4 = obj->book(5, 15);  // Returns false
bool param_5 = obj->book(5, 10);  // Returns true
bool param_6 = obj->book(25, 55); // Returns true

Clarifying Questions:

1. What is the range of the start and end parameters?
   • They are typically within 1 to (10^9).
2. Are we guaranteed that start < end in each booking request?
   • Yes, start is always less than end.
3. Can bookings be modified or canceled after they have been added?
   • No, bookings are not modified or canceled once added.

Strategy:

To solve this problem, we can utilize two lists to keep track of the events:

• events: to store all events that are added.
• overlaps: to store overlapping ranges between events that already exist.

When a new booking request comes in:

1. We first check if it will cause triple booking by comparing it with existing overlaps.
2. If it does not create a triple booking, we update the overlaps list by checking the intersections between the new event and existing events.
3. Finally, we add the new event to the events list.

A helper function to find the intersection of two intervals will be useful.

Code:

#include <vector>
using namespace std;

class MyCalendarTwo {
public:
    MyCalendarTwo() {}

    bool book(int start, int end) {
        for (const auto& [os, oe] : overlaps) {
            if (start < oe && end > os) {  // Check for overlap
                return false;
            }
        }
        
        for (const auto& [es, ee] : events) {
            if (start < ee && end > es) {  // Check for overlap
                overlaps.push_back({max(start, es), min(end, ee)});
            }
        }
        
        events.push_back({start, end});
        return true;
    }

private:
    vector<pair<int, int>> events;
    vector<pair<int, int>> overlaps;
};

Time Complexity:

• book method: Suppose there are (N) existing events, then checking all overlaps and events takes (O(N)) in the worst case. Thus, the overall time complexity per booking is (O(N)).

This approach efficiently manages bookings while ensuring that triple bookings are avoided.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?