3 ms·
I am very bad at these things when put in a spot. OTOH if you would let me pace around for a bit and stay invisible for a few minutes then its not too bad. Hav
by srean 12y ago
I am very bad at these things when put in a spot. OTOH if you would let me pace around for a bit and stay invisible for a few minutes then its not too bad.
Havent checked for correctness, but my off the cuff attempt would be to sort the left and right edges, then use a variable for the height and a stack. Proceed left to right. If I encounter a left edge and current height is lower than stack, push height on stack and update current height. If left edge lower than current, just push its value on the stack. If I encounter a right edge that matches current height pop height from stack in to current height. If right edge lower than current height, just pop the stack. The awkward case is when the left and right edges coincide.
- prawks 12y agoThis is pretty much the solution given. I've encountered a similar problem before (draw a bunch of overlapping squares with differing z-values) and done it similarly. The difficulty you end up having is that a stack doesn't give you a fast way to find the maximum height (what building/square) is on top at any given point. Hence, the article suggests a max heap.