Discuss the use and implementation for Interval trees.
You have N pairs of intervals, say integers. You're required to identify all intervals that overlap with each other in O(N logN) time. For example, if you have
{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}
the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example.
{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}
the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example.
No comments:
Post a Comment