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 naive notion that a mother naturally acquires the complex skills of childrearing simply because she has given birth now seems as absurd to me as enrolling in a nine-month class in composition and imagining that at the end of the course you are now prepared to begin writing War and Peace.”
—Mary Kay Blakely (20th century)
“Weaving spiders, come not here;
Hence, you longlegged spinners, hence!
Beetles black approach not near;
Worm nor snail, do no offence.”
—William Shakespeare (1564–1616)