Saturday, February 7, 2015

Find the interval that intersects with most intervals in a list of intervals

 Giving lots of intervals [ai, bi], find the interval (point) which intersects with the most number of intervals

 This is an interesting problem. The start point of the interval that intersects with the most number of intervals must be a start point of some interval in the list and the end point of it must be an end point of an interval in the list.

An interval

A point

So, the algorithm goes as follows: 
1. Sort the start and end points of all intervals in the list, this require an array or a list of 2 * size of the interval list. 
2. Go through the array/list of the start and end points, if we meet a start, increment count, if we meet an end, decrement the count. Why? Each time we encounter a start point, we have one more intersection, and each time we meet an end point, we lose an intersection, thus the position with the maximum count is the start point of the interval with the most intersections and the next position is the end point of it. 



Note the overlapping of the start and end point will not affect the count, since each start and end point will have a different index in the array. 




No comments:

Post a Comment