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:
““The days have outnumbered
my fingers and toes.
What can I count with now?”
Saying this,
the naive girl cries.”
—Hla Stavhana (c. 50 A.D.)
“The nearer people approach old age the closer they return to a semblance of childhood, until the time comes for them to depart this life, again like children, neither tired of living nor aware of death.”
—Desiderius Erasmus (c. 1466–1536)