Naive Approach
In a simple case, the intervals do not overlap and they can be inserted into a simple binary search tree and queried in O(log n) time. However, with arbitrarily overlapping intervals, there is no way to compare two intervals for insertion into the tree since orderings sorted by the beginning points or the ending points may be different. A naive approach might be to build two parallel trees, one ordered by the beginning point, and one ordered by the ending point of each interval. This allows discarding half of each tree in O(log n) time, but the results must be merged, requiring O(n) time. This gives us queries in O(n + log n) = O(n), which is no better than brute-force.
Interval trees solve this problem. This article describes two alternative designs for an interval tree, dubbed the centered interval tree and the augmented tree.
Read more about this topic: Interval Tree
Famous quotes containing the words naive and/or approach:
“Cynicism is full of naive disappointments.”
—Mason Cooley (b. 1927)
“F.R. Leavis’s “eat up your broccoli” approach to fiction emphasises this junkfood/wholefood dichotomy. If reading a novel—for the eighteenth century reader, the most frivolous of diversions—did not, by the middle of the twentieth century, make you a better person in some way, then you might as well flush the offending volume down the toilet, which was by far the best place for the undigested excreta of dubious nourishment.”
—Angela Carter (1940–1992)