giving lots of intervals [ai, bi], find a interval which intersect with the most number of intervals

Question

Given lots of intervals [ai, bi], find the interval that intersects the most number of intervals. Can we do this in O(nlogn) or better? I can think only of a n^2 approach.

Answer 1

Suppose the intervals are given as (a1,b1), ..., (an,bn). Make a sorted array of length 2n where ties are broken by

• if ai = aj, then put ai first iff bi < bj
• if bi = bj, then put bi first iff ai < aj
• if ai = bj, then put ai first

Mark each point as an a or a b (maybe keep a binary array of length 2n to do this). Walk through the array(s) keeping track of how many intervals touch the given point (running total of as minus running total of bs). The maximum number encountered happens at the interval with the most overlap.

This is O(n log n) due to the sorting of the intervals.