Let's say you are given a set of intervals (1,5), (6,10), (3,8), (7,9). The output I expect is 3 since there are maximum 3 intervals (3,8), (6,10) and (7,9) that intersect with each other. Note that, (1,5) and (3,8) also intersect with each other but that's only 2 of them. So the answer here is going to be 3, since 3 is the maximum number of intervals that intersect with each other.
What are some efficient ways of finding it? I guess the first step would be to sort the intervals according to the starting value. Any suggestions after that?
The standard solution is to process the intervals into a set of (begin,end) points. For example (1,3)
generates {1, begin}
, {3, end}
. Then sort the points and scan left to right, counting begin
as +1, end
as -1. The max value reached by the counter is the maximum number of overlapping intervals.
This is the intermediate array generated from the example in the question:
[(1, 'begin'),
(3, 'begin'),
(5, 'end'),
(6, 'begin'),
(7, 'begin'), # <--- counter reaches 3, its maximum value here.
(8, 'end'),
(9, 'end'), (10, 'end')]
There is a minor tricky point here. Does (1,end)
go before or after (1,begin)
? If you treat intervals as open, then it should go before - this way (0,1)
& (1,2)
won't be counted as intersecting. Otherwise it should go after and these intervals will count as intersecting ones.
Well, you can sort the intervals based on the start so if you have: (1,5) , (4,8) , (2,3)
They will be sorted: (1,5) , (2,3) , (4,8)
Then you will check the start of each interval against the highest End you found If the start is less than the end then there's an intersection
int highestEnd = intervals[0].end; // The highest end would be the end of the first interval
int numOfIntersections = 0;
for(int i = 1; i < intervalsSize; i++){
if(intervals[i].start < highestEnd)
numOfIntersections++;
if(intervals[i].end > highestEnd)
highestEnd = intervals[i].end;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With