arrays - Given a set of intervals, how to find the maximum number of intersections among them,

Question

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?

Answer 1

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.