引述《DJYOSHITAKA (franchouchouISBEST)》之铭言：
: 然后又多写一题
: 732. My Calendar III
: 算是经典的meeting room题目吧
: 直接sortedlist 又拿下一个hard
看dj宝才跑来写
第一个想法是维护区间 segment tree
可是他input 一个一个来怎么做我不会
1e9是不是要离散化
偷看解答发现大家都用map n^2 放完扫一遍
可是只有400 call 所以n = 400
n^2 = 160000
80 ms 好直觉喔
写完map之后在找有没有人用线段树写
后面好多
动态开点 太酷惹==
hashmap 500ms
link node 200ms
n =1e9
logn = 30
400*30 怎么都跑输 400*400
// segment tree
class Node{
public:
int val, lz;
Node *l, *r;
Node(){
val = 0; // count interval
lz = 0; // lazy
l = nullptr;
r = nullptr;
};
};
class Segment_tree{
public:
Node* root;
int tree_val;
Segment_tree(){
root = new Node();
tree_val = 0;
}
void push(Node* nd, int s, int e, int tl = 0, int tr = 1e9){
// out of range
if(e < tl || tr < s) return;
if(s <= tl && tr <= e){
nd->val++;
nd->lz++;
}
else{
int mid = (tl + tr) / 2;
if(nd->l == nullptr) nd->l = new Node();
if(nd->r == nullptr) nd->r = new Node();
push(nd->l, s, e, tl, mid);
push(nd->r, s, e, mid+1, tr);
nd->val = nd->lz + max(nd->l->val, nd->r->val);
}
if(nd == root) {
tree_val = nd->val;
}
}
};
class MyCalendarThree {
public:
Segment_tree tree;
MyCalendarThree() {
}
int book(int s, int e) {
tree.push(tree.root, s, e-1 );
return tree.tree_val;
}
/*
// map is too slow
unordered_map<int, int> seg, lazy;
void update(int id, int s, int e, int tl, int tr){
// out of range
if(e < tl || tr < s) return;
if(s <= tl && tr <= e){
lazy[id]++;
seg[id]++;
}
else{
int mid = (tl + tr) / 2;
update(2*id, s, e, tl, mid);
update(2*id + 1, s, e, mid+1, tr);
seg[id] = lazy[id] + max(seg[2*id], seg[2*id + 1]);
}
}
int book(int s, int e) {
update(1, s, e-1, 0, 1e9);
return seg[1];
}
*/
};
/**
* Your MyCalendarThree object will be instantiated and called as such:
* MyCalendarThree* obj = new MyCalendarThree();
* int param_1 = obj->book(startTime,endTime);
*/