Code Implementation

class MyCalendar:
    def __init__(self):
        self.bookings = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.bookings:
            if max(s, start) < min(e, end):
                return False
        self.bookings.append((start, end))
        return True
      

class MyCalendar {
public:
    vector<pair<int, int>> bookings;
    MyCalendar() {}

    bool book(int start, int end) {
        for (auto &[s, e] : bookings) {
            if (max(s, start) < min(e, end))
                return false;
        }
        bookings.push_back({start, end});
        return true;
    }
};
      

class MyCalendar {
    private List<int[]> bookings;

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

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

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

MyCalendar.prototype.book = function(start, end) {
    for (const [s, e] of this.bookings) {
        if (Math.max(s, start) < Math.min(e, end))
            return false;
    }
    this.bookings.push([start, end]);
    return true;
};
      

Problem Description

The My Calendar I problem asks you to design a calendar system that allows users to book time intervals, but only if the new booking does not overlap with any existing bookings. Each booking is represented as a half-open interval [start, end), where start is inclusive and end is exclusive. You will implement a class with a book(start, end) method that returns True if the new event can be booked without conflict, or False otherwise.

• Each call to book must ensure that no two events overlap.
• Events are stored and checked in the order they are added.
• There is no need to optimize for high performance in this version; correctness is the main goal.

Thought Process

The core challenge is to ensure that every new booking does not overlap with any previous bookings. Initially, we can approach this by considering every existing booking and checking for overlap with the new interval. If any overlap is found, we reject the booking.

A brute-force solution would simply store all previous bookings and, for each new request, scan through all of them to check for conflicts. While this is not the most efficient, it is simple and works well for the constraints given in this problem.

As we think about optimization, we might consider sorting the bookings or using more advanced data structures, but for the basic version, a straightforward linear scan is both acceptable and easy to implement.

Solution Approach

Let's break down the algorithm step by step:

1. Store Bookings: Maintain a list (or array) to store all the successfully booked intervals.
2. Overlap Check: For each new booking request [start, end), iterate over all existing bookings. For each existing booking [s, e), check if:
   • max(s, start) < min(e, end)
   This condition means the intervals overlap. If so, return False.
3. Add Booking: If no overlaps are found, add the new interval to the list of bookings and return True.

This approach is simple and ensures correctness. We use a list because it allows easy iteration and appending, which is all we need for this problem.

Example Walkthrough

Let's walk through an example sequence of bookings:

• Call book(10, 20): The calendar is empty, so this booking is added. Returns True.
• Call book(15, 25): The current booking is [10, 20). Since max(10, 15) = 15 < min(20, 25) = 20, there is an overlap. Returns False.
• Call book(20, 30): The only booking is [10, 20). Since max(10, 20) = 20 is not less than min(20, 30) = 20, there is no overlap. The new booking is added. Returns True.

The process checks all previous bookings for each new booking, ensuring no overlaps are ever introduced.

Time and Space Complexity

Brute-force Approach:

• Time Complexity: Each book call checks all previous bookings, so if there are n bookings, each call takes O(n) time.
• Space Complexity: All bookings are stored, so space is O(n).

• Using advanced data structures (like a balanced BST) could reduce the time per booking to O(log n), but that is not necessary for this version of the problem.

Summary

The solution to the My Calendar I problem is straightforward: for each new booking, check for overlaps with all existing bookings and only add the new booking if there are no conflicts. This simple linear approach is effective for the problem's constraints and demonstrates the importance of careful interval overlap checking. While more efficient solutions exist, this method is clear, easy to implement, and sufficient for the task.