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.)
“So live that when thy summons comes to join
The innumerable caravan that moves
To that mysterious realm, where each shall take
His chamber in the silent halls of death,
Thou go not, like the quarry-slave at night,
Scourged to his dungeon, but, sustained and soothed
By an unfaltering trust, approach thy grave
Like one who wraps the drapery of his couch
About him and lies down to pleasant dreams.”
—William Cullen Bryant (1794–1878)