mI'm receiving TLE on 17/20 test's. I'm doing this task with interval tree, and my init function doesn't work fast enough. Could someone look at my code and tell me how to do it faster ?
http://www.z-trening.com/submit.php?subm_stat=1&submit=7100097138
Your init function has linear complexity, and that's something you wouldn't like to have in an interval tree. The main reason why it's so slow is the fact that you always descend to the leaf nodes of the queried interval. In general, your interval tree operations should visit O( lg N ) nodes, which is achieved by terminating the recursion when a node you visited fully covers a part of the queried interval. Therefore the second 'if' in your init function should check if the current node's interval fully resides inside the query one...
Let's say that I want to add boxes on [ 1 , 4 ] , so when i get to a node that covers that interval I'll store at this node some info , and I wont go any further. But when i want to get number of occupied places on [ 1 , 2 ], how can I get this when i don't know anything about this interval ?
O
/ \
O O
/ \ / \
[{O O}O O ]
Info from [1 , 4 ] is on top , but how to get info from { 1 , 2 } ?
you can also use the info you gathered on your path from the root... if you saw a node which is marked as fully covered.. you know that the whole interval you jump in in your recursion is also covered.. so, if a node's interval is fully covered you can return its full length ( if it's in the queried one, or cuts it somehow ).
Thanks, I finally caught some time and solved it .
