Overlapping intervals
Once again this is an interview question that was asked to me at Adobe.
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.
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.
use interval tree..
ReplyDeletePreprocessing time for Interval tree is O(nlogn);
ReplyDeleteHow it will take O(n) time?
If you please practically elaborate your approach it will be helpful.
sorry that was typo error.it should be o(nlogn)
ReplyDeleteSir, why do we need an interval tree.
ReplyDeletePlz check my approach.
Assume the elements are struct/pairs of { start_time, finish_time };
Apply randomised quick-sort algorithm to sort the array based on finish_time.
Now for each element ,we can check if its start_time overlaps with the finish_time of previous element.
Doubt :- What if the array can has two exclusive groups which are non-overlapping, but each group has k elements which are overlapping.
Which group of elements to print.
The array approach can be trimmed to print each such group separately