My Calendar II

MediumArrayBinary SearchDesignSegment TreePrefix SumOrdered Set

Solution

export class MyCalendarTwo {
  private readonly bookings: [number, number][];
  private readonly doubleBookings: [number, number][];
 
  constructor() {
    this.bookings = [];
    this.doubleBookings = [];
  }
 
  book(start: number, end: number): boolean {
    for (const booking of this.doubleBookings) {
      if (Math.max(start, booking[0]) < Math.min(end, booking[1])) {
        return false;
      }
    }
 
    for (const booking of this.bookings) {
      if (Math.max(start, booking[0]) < Math.min(end, booking[1])) {
        this.doubleBookings.push([Math.max(start, booking[0]), Math.min(end, booking[1])]);
      }
    }
    this.bookings.push([start, end]);
    return true;
  }
}

Complexity

  • Time: O(N)
  • Space: O(N)