实现一个 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]。
方法一：差分
利用有序哈希表实现。
时间复杂度
方法二：线段树
线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过
- 线段树的每个节点代表一个区间；
- 线段树具有唯一的根节点，代表的区间是整个统计范围，如
$[1,N]$ ； - 线段树的每个叶子节点代表一个长度为
$1$ 的元区间$[x, x]$ ； - 对于每个内部节点
$[l,r]$ ，它的左儿子是$[l,mid]$ ，右儿子是$[mid+1,r]$ , 其中$mid = ⌊(l+r)/2⌋$ (即向下取整)。
对于本题，线段树节点维护的信息有：
- 区间范围内被预定的次数的最大值
$v$ - 懒标记
$add$
由于时间范围为
时间复杂度
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 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 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 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 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);
*/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 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);
*/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);
*/