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