# 732. My Calendar III

## Description

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

• MyCalendarThree() Initializes the object.
• int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3



Constraints:

• 0 <= startTime < endTime <= 109
• At most 400 calls will be made to book.

## Solutions

Same as https://leetcode.ca/2017-11-30-731-My-Calendar-II/, just changing from 2 to k.

• class Node {
Node left;
Node right;
int l;
int r;
int mid;
int v;
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;
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);
}
Node left = node.left, right = node.right;
}
}
}

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;

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

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;
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);
Node* left = node->left;
Node* right = node->right;
}
}
};

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);
*/

• from sortedcontainers import SortedDict

class MyCalendarThree:
def __init__(self):
self.timeline = SortedDict()

def book(self, start: int, end: int) -> int:
self.timeline[start] = self.timeline.get(start, 0) + 1
self.timeline[end] = self.timeline.get(end, 0) - 1

return max(accumulate(list(self.timeline.values())))

############

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

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
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)

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(object):
def __init__(self, start, end, c):
self.start = start
self.end = end
self.count = c
self.left = None
self.right = None

class MyCalendarThree(object):
def __init__(self):
self.root = None
self.maxK = 1

def book_helper(self, root, start, end, c):
if root == None:
return Node(start, end, c)
if start >= root.end:
#不能写成return self.boook_helper()，因为要进行树的构建和修改，一定要赋值给root.right
root.right = self.book_helper(root.right, start, end, c)
elif end <= root.start:
root.left = self.book_helper(root.left, start, end, c)
else:
intervals = sorted([start, end, root.start, root.end])
root_l, root_r = root.start, root.end
root.start, root.end = intervals[1], intervals[2]
root.left = self.book_helper(root.left, intervals[0], intervals[1], c if start <= root_l else root.count)
root.right = self.book_helper(root.right, intervals[2], intervals[3], c if end >= root_r else root.count)
root.count += c
self.maxK = max(root.count, self.maxK)
return root

def book(self, start, end):
"""
:type start: int
:type end: int
:rtype: int
"""
self.root = self.book_helper(self.root, start, end, 1)
return self.maxK

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


• type node struct {
left      *node
right     *node
l, mid, r 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
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)
}
}
}

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);
*/