algoadvance

Leetcode 729. My Calendar I

Problem Statement

You are implementing a program to help manage a calendar with the ability to book new events. Each new event you want to book can be represented as a pair of integers (start, end) which represents the start and end times of the event. For this problem, assume that the events are half-open intervals, i.e., [start, end), where start is inclusive and end is exclusive.

A new event can be added to the calendar if it does not overlap with any of the existing events in the calendar. An event x overlaps with another event y if x’s start time is less than y’s end time and x’s end time is greater than y’s start time.

Implement the MyCalendar class:

• MyCalendar() Initializes the calendar object.
• bool book(int start, int end) Returns true if the event can be added to the calendar without causing a conflict. Otherwise, returns false and doesn’t add the event to the calendar.

Example:

MyCalendar cal = new MyCalendar();
cal.book(10, 20); // returns true
cal.book(15, 25); // returns false
cal.book(20, 30); // returns true

Constraints:

• 0 <= start < end <= 10^9
• At most 1000 calls will be made to book.

Clarifying Questions

1. Are the start and end times always given in increasing order within a specific book call?
2. Is there any restriction on how many events can be booked at most?
3. Should I consider edge cases like very large inputs regarding performance?

Strategy

To solve this problem:

• We can use a list to store pairs of (start, end) representing the booked events.
• Each time an event is to be booked, iterate through the list and check for overlaps with the existing events.
• If no overlap is found, add the new event to the list and return true; otherwise, return false.

Steps:

1. Initialize the calendar with an empty list.
2. For each new booking request, check it against existing events in the list to ensure there is no overlap.
3. If there’s no conflict, append the new event to the list; otherwise, reject it.

The time complexity for each booking operation is O(n), where n is the number of events already booked.

Code

#include <vector>

class MyCalendar {
private:
    std::vector<std::pair<int, int>> calendar;

public:
    MyCalendar() { }
    
    bool book(int start, int end) {
        for (const auto &event : calendar) {
            if (start < event.second && end > event.first) {
                return false; // There's an overlap
            }
        }
        calendar.push_back({start, end});
        return true;
    }
};

Time Complexity

Each call to book involves checking all previously booked events. In the worst case, this will be O(n), where n is the number of previously booked events. Given the constraint that there will be at most 1000 calls to book, this is manageable within the problem limits.

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?