Re: [閒聊] 每日leetcode

引述《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); */ ----- Sent from JPTT on my iPad --
※ 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1726948178.A.1CB.html