Question

731. 我的日程安排表 II

English Version

题目描述

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

 

示例：

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
解释： 
前两个日程安排可以添加至日历中。 第三个日程安排会导致双重预订，但可以添加至日历中。
第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。
第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。
第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；
时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。

 

提示：

• 每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
• 调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。

解法

方法一：差分

利用有序哈希表实现。

时间复杂度 $O(n^2)$，其中 $n$ 表示日程安排的数量。

from sortedcontainers import SortedDict


class MyCalendarTwo:
  def __init__(self):
    self.sd = SortedDict()

  def book(self, start: int, end: int) -> bool:
    self.sd[start] = self.sd.get(start, 0) + 1
    self.sd[end] = self.sd.get(end, 0) - 1
    s = 0
    for v in self.sd.values():
      s += v
      if s > 2:
        self.sd[start] -= 1
        self.sd[end] += 1
        return False
    return True


# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)

class MyCalendarTwo {
  private Map<Integer, Integer> tm = new TreeMap<>();

  public MyCalendarTwo() {
  }

  public boolean book(int start, int end) {
    tm.put(start, tm.getOrDefault(start, 0) + 1);
    tm.put(end, tm.getOrDefault(end, 0) - 1);
    int s = 0;
    for (int v : tm.values()) {
      s += v;
      if (s > 2) {
        tm.put(start, tm.get(start) - 1);
        tm.put(end, tm.get(end) + 1);
        return false;
      }
    }
    return true;
  }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */

class MyCalendarTwo {
public:
  map<int, int> m;

  MyCalendarTwo() {
  }

  bool book(int start, int end) {
    ++m[start];
    --m[end];
    int s = 0;
    for (auto& [_, v] : m) {
      s += v;
      if (s > 2) {
        --m[start];
        ++m[end];
        return false;
      }
    }
    return true;
  }
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */

type MyCalendarTwo struct {
  *redblacktree.Tree
}

func Constructor() MyCalendarTwo {
  return MyCalendarTwo{redblacktree.NewWithIntComparator()}
}

func (this *MyCalendarTwo) Book(start int, end int) bool {
  add := func(key, val int) {
    if v, ok := this.Get(key); ok {
      this.Put(key, v.(int)+val)
    } else {
      this.Put(key, val)
    }
  }
  add(start, 1)
  add(end, -1)
  s := 0
  it := this.Iterator()
  for it.Next() {
    s += it.Value().(int)
    if s > 2 {
      add(start, -1)
      add(end, 1)
      return false
    }
  }
  return true
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(start,end);
 */

方法二：线段树

线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 $log(width)$。更新某个元素的值，只需要更新 $log(width)$ 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。

• 线段树的每个节点代表一个区间；
• 线段树具有唯一的根节点，代表的区间是整个统计范围，如 $[1,N]$；
• 线段树的每个叶子节点代表一个长度为 $1$ 的元区间 $[x, x]$；
• 对于每个内部节点 $[l,r]$，它的左儿子是 $[l,mid]$，右儿子是 $[mid+1,r]$, 其中 $mid = ⌊(l+r)/2⌋$ (即向下取整)。

对于本题，线段树节点维护的信息有：

1. 区间范围内被预定的次数的最大值 $v$
2. 懒标记 $add$

由于时间范围为 $10^9$，非常大，因此我们采用动态开点。

时间复杂度 $O(nlogn)$，其中 $n$ 表示日程安排的数量。

class Node:
  def __init__(self, l, r):
    self.left = None
    self.right = None
    self.l = l
    self.r = r
    self.mid = (l + r) >> 1
    self.v = 0
    self.add = 0


class SegmentTree:
  def __init__(self):
    self.root = Node(1, int(1e9 + 1))

  def modify(self, l, r, v, node=None):
    if l > r:
      return
    if node is None:
      node = self.root
    if node.l >= l and node.r <= r:
      node.v += v
      node.add += v
      return
    self.pushdown(node)
    if l <= node.mid:
      self.modify(l, r, v, node.left)
    if r > node.mid:
      self.modify(l, r, v, node.right)
    self.pushup(node)

  def query(self, l, r, node=None):
    if l > r:
      return 0
    if node is None:
      node = self.root
    if node.l >= l and node.r <= r:
      return node.v
    self.pushdown(node)
    v = 0
    if l <= node.mid:
      v = max(v, self.query(l, r, node.left))
    if r > node.mid:
      v = max(v, self.query(l, r, node.right))
    return v

  def pushup(self, node):
    node.v = max(node.left.v, node.right.v)

  def pushdown(self, node):
    if node.left is None:
      node.left = Node(node.l, node.mid)
    if node.right is None:
      node.right = Node(node.mid + 1, node.r)
    if node.add:
      node.left.v += node.add
      node.right.v += node.add
      node.left.add += node.add
      node.right.add += node.add
      node.add = 0


class MyCalendarTwo:
  def __init__(self):
    self.tree = SegmentTree()

  def book(self, start: int, end: int) -> bool:
    if self.tree.query(start + 1, end) >= 2:
      return False
    self.tree.modify(start + 1, end, 1)
    return True


# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)

class Node {
  Node left;
  Node right;
  int l;
  int r;
  int mid;
  int v;
  int add;
  public Node(int l, int r) {
    this.l = l;
    this.r = r;
    this.mid = (l + r) >> 1;
  }
}

class SegmentTree {
  private Node root = new Node(1, (int) 1e9 + 1);

  public SegmentTree() {
  }

  public void modify(int l, int r, int v) {
    modify(l, r, v, root);
  }

  public void modify(int l, int r, int v, Node node) {
    if (l > r) {
      return;
    }
    if (node.l >= l && node.r <= r) {
      node.v += v;
      node.add += v;
      return;
    }
    pushdown(node);
    if (l <= node.mid) {
      modify(l, r, v, node.left);
    }
    if (r > node.mid) {
      modify(l, r, v, node.right);
    }
    pushup(node);
  }

  public int query(int l, int r) {
    return query(l, r, root);
  }

  public int query(int l, int r, Node node) {
    if (l > r) {
      return 0;
    }
    if (node.l >= l && node.r <= r) {
      return node.v;
    }
    pushdown(node);
    int v = 0;
    if (l <= node.mid) {
      v = Math.max(v, query(l, r, node.left));
    }
    if (r > node.mid) {
      v = Math.max(v, query(l, r, node.right));
    }
    return v;
  }

  public void pushup(Node node) {
    node.v = Math.max(node.left.v, node.right.v);
  }

  public void pushdown(Node node) {
    if (node.left == null) {
      node.left = new Node(node.l, node.mid);
    }
    if (node.right == null) {
      node.right = new Node(node.mid + 1, node.r);
    }
    if (node.add != 0) {
      Node left = node.left, right = node.right;
      left.add += node.add;
      right.add += node.add;
      left.v += node.add;
      right.v += node.add;
      node.add = 0;
    }
  }
}

class MyCalendarTwo {
  private SegmentTree tree = new SegmentTree();

  public MyCalendarTwo() {
  }

  public boolean book(int start, int end) {
    if (tree.query(start + 1, end) >= 2) {
      return false;
    }
    tree.modify(start + 1, end, 1);
    return true;
  }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */

class Node {
public:
  Node* left;
  Node* right;
  int l;
  int r;
  int mid;
  int v;
  int add;

  Node(int l, int r) {
    this->l = l;
    this->r = r;
    this->mid = (l + r) >> 1;
    this->left = this->right = nullptr;
    v = add = 0;
  }
};

class SegmentTree {
private:
  Node* root;

public:
  SegmentTree() {
    root = new Node(1, 1e9 + 1);
  }

  void modify(int l, int r, int v) {
    modify(l, r, v, root);
  }

  void modify(int l, int r, int v, Node* node) {
    if (l > r) return;
    if (node->l >= l && node->r <= r) {
      node->v += v;
      node->add += v;
      return;
    }
    pushdown(node);
    if (l <= node->mid) modify(l, r, v, node->left);
    if (r > node->mid) modify(l, r, v, node->right);
    pushup(node);
  }

  int query(int l, int r) {
    return query(l, r, root);
  }

  int query(int l, int r, Node* node) {
    if (l > r) return 0;
    if (node->l >= l && node->r <= r) return node->v;
    pushdown(node);
    int v = 0;
    if (l <= node->mid) v = max(v, query(l, r, node->left));
    if (r > node->mid) v = max(v, query(l, r, node->right));
    return v;
  }

  void pushup(Node* node) {
    node->v = max(node->left->v, node->right->v);
  }

  void pushdown(Node* node) {
    if (!node->left) node->left = new Node(node->l, node->mid);
    if (!node->right) node->right = new Node(node->mid + 1, node->r);
    if (node->add) {
      Node* left = node->left;
      Node* right = node->right;
      left->v += node->add;
      right->v += node->add;
      left->add += node->add;
      right->add += node->add;
      node->add = 0;
    }
  }
};

class MyCalendarTwo {
public:
  SegmentTree* tree = new SegmentTree();

  MyCalendarTwo() {
  }

  bool book(int start, int end) {
    if (tree->query(start + 1, end) >= 2) return false;
    tree->modify(start + 1, end, 1);
    return true;
  }
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */

type node struct {
  left    *node
  right   *node
  l, mid, r int
  v, add  int
}

func newNode(l, r int) *node {
  return &node{
    l:   l,
    r:   r,
    mid: int(uint(l+r) >> 1),
  }
}

type segmentTree struct {
  root *node
}

func newSegmentTree() *segmentTree {
  return &segmentTree{
    root: newNode(1, 1e9+1),
  }
}

func (t *segmentTree) modify(l, r, v int, n *node) {
  if l > r {
    return
  }
  if n.l >= l && n.r <= r {
    n.v += v
    n.add += v
    return
  }
  t.pushdown(n)
  if l <= n.mid {
    t.modify(l, r, v, n.left)
  }
  if r > n.mid {
    t.modify(l, r, v, n.right)
  }
  t.pushup(n)
}

func (t *segmentTree) query(l, r int, n *node) int {
  if l > r {
    return 0
  }
  if n.l >= l && n.r <= r {
    return n.v
  }
  t.pushdown(n)
  v := 0
  if l <= n.mid {
    v = max(v, t.query(l, r, n.left))
  }
  if r > n.mid {
    v = max(v, t.query(l, r, n.right))
  }
  return v
}

func (t *segmentTree) pushup(n *node) {
  n.v = max(n.left.v, n.right.v)
}

func (t *segmentTree) pushdown(n *node) {
  if n.left == nil {
    n.left = newNode(n.l, n.mid)
  }
  if n.right == nil {
    n.right = newNode(n.mid+1, n.r)
  }
  if n.add != 0 {
    n.left.add += n.add
    n.right.add += n.add
    n.left.v += n.add
    n.right.v += n.add
    n.add = 0
  }
}

type MyCalendarTwo struct {
  tree *segmentTree
}

func Constructor() MyCalendarTwo {
  return MyCalendarTwo{newSegmentTree()}
}

func (this *MyCalendarTwo) Book(start int, end int) bool {
  if this.tree.query(start+1, end, this.tree.root) >= 2 {
    return false
  }
  this.tree.modify(start+1, end, 1, this.tree.root)
  return true
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(start,end);
 */