729.我的日程安排表I

链接：729.我的日程安排表I
难度：Medium
标签：设计、线段树、数组、二分查找、有序集合
简介：实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

题解 1 - typescript

• 编辑时间：2022-07-05
• 执行用时：188ms
• 内存消耗：50.3MB
• 编程语言：typescript
• 解法介绍：构建 rbtree，每次通过 start、end 查找他最近的值然后进行比较。

let NIL: RBNode<any>;
class RBNode<T> {
  constructor(public key: T, public color = 0, public lchild = NIL, public rchild = NIL) {}
  hasRedChild() {
    return this.lchild.color === 0 || this.rchild.color === 0;
  }
}
NIL = new RBNode(0, 1);
class RBTree<T extends Array<any>> {
  root: RBNode<T> = NIL;
  constructor(public compare: (v1: T, v2: T) => number) {}
  print(node = this.root, init = true) {
    if (node == NIL) return;
    if (init) console.log('===[RBTree Print]===');
    console.log(`${node.key}, (${node.lchild.key}, ${node.rchild.key})`);
    this.print(node.lchild, false);
    this.print(node.rchild, false);
  }
  rotateLeft(node: RBNode<T>) {
    const newNode = node.rchild;
    node.rchild = newNode.lchild;
    newNode.lchild = node;
    return newNode;
  }
  rotateRight(node: RBNode<T>) {
    const newNode = node.lchild;
    node.lchild = newNode.rchild;
    newNode.rchild = node;
    return newNode;
  }
  insert(key: T) {
    this.root = this._insert(this.root, key);
    this.root.color = 1;
  }
  _insert(node: RBNode<T>, key: T) {
    if (node === NIL) return new RBNode(key);
    const compare = this.compare(key, node.key);
    if (compare === 0) {
      node.key = key;
      return node;
    }
    if (compare > 0) node.rchild = this._insert(node.rchild, key);
    else node.lchild = this._insert(node.lchild, key);
    return this._insertMaintain(node);
  }
  _insertMaintain(node: RBNode<T>) {
    if (!node.hasRedChild()) return node;
    if (
      !(node.lchild.color === 0 && node.lchild.hasRedChild()) &&
      !(node.rchild.color === 0 && node.rchild.hasRedChild())
    )
      return node;
    if (node.lchild.color === 1) {
      if (node.rchild.lchild.color === 0) node.rchild = this.rotateRight(node.rchild);
      node = this.rotateLeft(node);
    } else if (node.rchild.color === 1) {
      if (node.lchild.rchild.color === 0) node.lchild = this.rotateLeft(node.lchild);
      node = this.rotateRight(node);
    }
    node.color = 0;
    node.lchild.color = node.rchild.color = 1;
    return node;
  }
  remove(key: T) {
    this.root = this._remove(this.root, key);
    this.root.color = 1;
  }
  _remove(node: RBNode<T>, key: T) {
    if (node == NIL) return node;
    const compare = this.compare(key, node.key);
    if (compare > 0) node.rchild = this._remove(node.rchild, key);
    else if (compare < 0) node.lchild = this._remove(node.lchild, key);
    else {
      if (node.lchild === NIL || node.rchild === NIL) {
        const tmp = node.lchild === NIL ? node.rchild : node.lchild;
        tmp.color += node.color;
        return tmp;
      } else {
        let tmp = node.lchild;
        while (tmp.rchild !== NIL) tmp = tmp.rchild;
        node.key = tmp.key;
        node.lchild = this._remove(node.lchild, tmp.key);
      }
    }
    return this._removeMaintain(node);
  }
  _removeMaintain(node: RBNode<T>) {
    if (node.lchild.color !== 2 && node.rchild.color !== 2) return node;
    if (node.hasRedChild()) {
      let type = 0;
      node.color = 0;
      if (node.lchild.color === 0) node = this.rotateRight(node);
      else (node = this.rotateLeft(node)), (type = 1);
      node.color = 1;
      if (type === 1) node.lchild = this._removeMaintain(node.lchild);
      else node.rchild = this._removeMaintain(node.rchild);
      return node;
    }
    if (
      (node.lchild.color === 1 && !node.lchild.hasRedChild()) ||
      (node.rchild.color === 1 && !node.rchild.hasRedChild())
    ) {
      node.color += 1;
      node.lchild.color -= 1;
      node.rchild.color -= 1;
      return node;
    }
    if (node.lchild.color === 1) {
      if (node.lchild.lchild.color !== 0) {
        node.lchild.color = 0;
        node.lchild = this.rotateLeft(node.lchild);
        node.lchild.color = 1;
      }
      node.lchild.color = node.color;
      node.rchild.color = 1;
      node = this.rotateRight(node);
    } else {
      if (node.rchild.rchild.color !== 0) {
        node.rchild.color = 0;
        node.rchild = this.rotateRight(node.rchild);
        node.rchild.color = 1;
      }
      node.rchild.color = node.color;
      node.lchild.color = 1;
      node = this.rotateLeft(node);
    }
    node.lchild.color = node.rchild.color = 1;
    return node;
  }
  successor(node: RBNode<T>) {
    let successor = NIL;
    if (node.rchild) {
      successor = node.rchild;
      while (successor.lchild) successor = successor!.lchild;
      return successor;
    }
    let tmp = this.root;
    while (tmp) {
      if (tmp.key > node.key) {
        successor = tmp;
        tmp = tmp.lchild;
      } else {
        tmp = tmp.rchild;
      }
    }
    return tmp;
  }
  check([start, end]: T): boolean {
    let node = this.root;
    while (node !== NIL) {
      if (node.key[0] >= end) node = node.lchild;
      else if (node.key[1] <= start) node = node.rchild;
      else break;
    }
    if (node === NIL) return true;
    let tmp = node;
    while (tmp !== NIL && tmp.key[1] >= start) {
      const [tstart, tend] = tmp.key;
      if (
        (start > tstart && start < tend) ||
        (end > tstart && end < tend) ||
        (start <= tstart && end >= tend)
      )
        return false;
      tmp = this.successor(tmp);
    }
    return true;
  }
}
class MyCalendar {
  tree = new RBTree<number[]>((v1, v2) => v1[0] - v2[0]);
  book(start: number, end: number): boolean {
    const ans = this.tree.check([start, end]);
    if (ans) this.tree.insert([start, end]);
    return ans;
  }
}

题解 2 - python

• 编辑时间：2025-01-02
• 执行用时：73ms
• 内存消耗：18.5MB
• 编程语言：python
• 解法介绍：有序遍历

from sortedcontainers import SortedList
class MyCalendar:
    def __init__(self):
        self.list = SortedList()
    def book(self, startTime: int, endTime: int) -> bool:
        idx = self.list.bisect_left((startTime, endTime))
        if idx - 1 >= 0 and self.list[idx - 1][1] > startTime: return False
        if idx < len(self.list) and self.list[idx][0] < endTime: return False
        self.list.add((startTime, endTime))
        return True