当 k
个日程安排有一些时间上的交叉时(例如 k
个日程安排都在同一时间内),就会产生 k
次预订。
给你一些日程安排 [start, end)
,请你在每个日程安排添加后,返回一个整数 k
,表示所有先前日程安排会产生的最大 k
次预订。
实现一个 MyCalendarThree
类来存放你的日程安排,你可以一直添加新的日程安排。
MyCalendarThree()
初始化对象。int book(int start, int end)
返回一个整数k
,表示日历中存在的k
次预订的最大值。
示例:
输入: ["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] 输出: [null, 1, 1, 2, 3, 3, 3] 解释: MyCalendarThree myCalendarThree = new MyCalendarThree(); myCalendarThree.book(10, 20); // 返回 1 ,第一个日程安排可以预订并且不存在相交,所以最大 k 次预订是 1 次预订。 myCalendarThree.book(50, 60); // 返回 1 ,第二个日程安排可以预订并且不存在相交,所以最大 k 次预订是 1 次预订。 myCalendarThree.book(10, 40); // 返回 2 ,第三个日程安排 [10, 40) 与第一个日程安排相交,所以最大 k 次预订是 2 次预订。 myCalendarThree.book(5, 15); // 返回 3 ,剩下的日程安排的最大 k 次预订是 3 次预订。 myCalendarThree.book(5, 10); // 返回 3 myCalendarThree.book(25, 55); // 返回 3
提示:
0 <= start < end <= 109
- 每个测试用例,调用
book
函数最多不超过400
次
方法一:线段树
线段树将整个区间分割为多个不连续的子区间,子区间的数量不超过
- 线段树的每个节点代表一个区间;
- 线段树具有唯一的根节点,代表的区间是整个统计范围,如
$[1,N]$ ; - 线段树的每个叶子节点代表一个长度为
$1$ 的元区间$[x, x]$ ; - 对于每个内部节点
$[l,r]$ ,它的左儿子是$[l,mid]$ ,右儿子是$[mid+1,r]$ , 其中$mid = ⌊(l+r)/2⌋$ (即向下取整)。
对于本题,线段树节点维护的信息有:
- 区间范围内被预定的次数的最大值
$v$ - 懒标记
$add$
由于时间范围为
时间复杂度
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 MyCalendarThree:
def __init__(self):
self.tree = SegmentTree()
def book(self, start: int, end: int) -> int:
self.tree.modify(start + 1, end, 1)
return self.tree.query(1, int(1e9 + 1))
# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# 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 MyCalendarThree {
private SegmentTree tree = new SegmentTree();
public MyCalendarThree() {
}
public int book(int start, int end) {
tree.modify(start + 1, end, 1);
return tree.query(1, (int) 1e9 + 1);
}
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree obj = new MyCalendarThree();
* int 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 MyCalendarThree {
public:
SegmentTree* tree;
MyCalendarThree() {
tree = new SegmentTree();
}
int book(int start, int end) {
tree->modify(start + 1, end, 1);
return tree->query(1, 1e9 + 1);
}
};
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree* obj = new MyCalendarThree();
* int 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),
}
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
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 MyCalendarThree struct {
tree *segmentTree
}
func Constructor() MyCalendarThree {
return MyCalendarThree{newSegmentTree()}
}
func (this *MyCalendarThree) Book(start int, end int) int {
this.tree.modify(start+1, end, 1, this.tree.root)
return this.tree.query(1, int(1e9)+1, this.tree.root)
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/