729. My Calendar I

Description

The MyCalendar class allows for scheduling events without overlaps. Each time an event is booked, it checks if the new event overlaps with any existing ones. If no overlap is found, the event is booked successfully; otherwise, the booking is rejected. This structure is useful for managing a calendar or booking system.

Intuition

The main challenge is checking whether the new event overlaps with any previously booked events. This can be done efficiently by comparing the start and end times of the new event with those of the existing ones. If the start time of the new event is earlier than the end time of a booked event and the end time of the new event is later than the start time of a booked event, the two events overlap.

Approach

1. Maintain a list (or equivalent structure) to keep track of all booked events.
2. For each new event, iterate through the booked events to check if the current event overlaps with any of the already booked events.
3. If an overlap is found, return false (indicating that the event can't be booked). Otherwise, book the event by adding it to the list and return true.
4. Use the condition max(start1, start2) < min(end1, end2) to determine if two events overlap.

Complexity

Time Complexity:

O(n), where n is the number of booked events. Each booking operation requires iterating through the list of booked events.

Space Complexity:

O(n), where n is the number of booked events, since we store each booked event in the list.

Code

C++

class MyCalendar {
public:
    vector> booked;

    MyCalendar() {
    }

    bool book(int start, int end) {
        for (auto &b : booked) {
            if (max(b.first, start) < min(b.second, end)) {
                return false;
            }
        }
        booked.push_back({start, end});
        return true;
    }
};

Python

class MyCalendar:

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

    def book(self, start: int, end: int) -> bool:
        for b in self.booked:
            if max(b[0], start) < min(b[1], end):
                return False
        self.booked.append([start, end])
        return True

Java

class MyCalendar {
    List booked;

    public MyCalendar() {
        booked = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] b : booked) {
            if (Math.max(b[0], start) < Math.min(b[1], end)) {
                return false;
            }
        }
        booked.add(new int[]{start, end});
        return true;
    }
}

JavaScript

var MyCalendar = function () {
    this.booked = [];

};

/** 
 * @param {number} start 
 * @param {number} end
 * @return {boolean}
 */

MyCalendar.prototype.book = function (start, end) {

    for (let booked of this.booked)
        if (Math.max(booked[0], start) < Math.min(booked[1], end))
            return false;
    this.booked.push([start, end])
    
    return true
};