3 ms·
My first thought was to dump the rectangles into an interval tree. Also O(n log n), but less space efficient since it always requires O(n) space regardless of t
by michaelmior 12y ago
My first thought was to dump the rectangles into an interval tree. Also O(n log n), but less space efficient since it always requires O(n) space regardless of the structure of the problem.
- brianpgordon 12y agoAre you sure that it's n log n? I think that the pyramid shaped configuration defeats this strategy by forcing the interval tree to report something on the order of n intervals with every query. So there are n queries on the interval tree, and each query takes log(n) + n time. Also, something interesting to note that I was thinking about yesterday is that you don't actually need to use an interval tree for this. You can use a range tree instead, which is simpler (to my mind). You only need an interval tree to do a certain kind of query which we never need to do: https://briangordon.github.io/images/range-interval.png https://briangordon.github.io/images/range-interval.png
- michaelmior 12y agoI'm not sure what you mean by the pyramid-shaped configuration. In any case, n queries taking log(n) + n time each is O(n log n). I think you're right that a range tree should work fine.
- brianpgordon 12y agoI mean this thing from the article: https://briangordon.github.io/images/worstcase.svg https://briangordon.github.io/images/worstcase.svg > n queries taking log(n) + n time each is O(n log n) No, it's O(n^2).
- michaelmior 12y agoWow, clearly commenting too late. Of course you're right :)