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.

Answer 2

Use interval trees: http://en.wikipedia.org/wiki/Interval_tree .

If you use centered interval tree, complexity is O(nlogn + m) where m is the total number of intersections (worst case m=n^2).

Answer 3

According to PengOne's answer, I do a simple implementation, using two n sort array instead of 2n array.

1) Construct two n arrays, one is sort by ai, another is sort by bi.
   make sure that if ai==aj, then bi<bj, but i before j, the same as b-array.
2) Walk through the b-array for each b, Do a binary search in a-array to find 
   index, make sure a[index]<=b<a[index+1]
3) find the max(index - i + 1), the the bi is the point we need.

Code

public int getPoint(List<Interval> intervals) {
    // validation
    if (intervals == null || intervals.size() == 0) {
        return 0;
    }
    List<Interval> sortA = sortByA(intervals);
    List<Interval> sortB = sortByB(intervals);
    int max = 0;
    int maxPoint = sortB.get(0).b;
    for (int i = 0; i < sortB.size(); i++) {
        Interval interval = sortB.get(i);
        // find B in sortA.
        int index = search(sortA, interval.b);
        int count = index - i + 1;
        if (count > max) {
            max = count;
            maxPoint = sortB.get(i).b;
        }
    }
    return maxPoint;
}

Answer 4

If the values ai and bi are not small integers < N then they can be reduced by sorting the indices in the list of all distinct ai and bi values.

Given the input "list" which contains all distinct ai and bi. The sorted index is in C#:

int[] index = Enumerable.Range(0, list.Count).OrderBy(i => list[i]).ToArray();

By inverting that permutation, then a value from 0 to N - 1 can be assigned to each ai and bi.

int[] values = invertPermutation(index);

ai can be replaced with values[location_of_ai_in_List]

Now given that the new ai and bi can be made < N there's a neat trick to find the maximum overlapping interval in O(N), as well as some other queries can be responded fast.

1. declare an array of N+1 elements:

   int[] sum = new int[N+1];

2. for each interval perform:

   sum[ai]++;

   sum[bi+1]--;

//Total complexity of this step is O(N) since we process each interval in O(1).

3. Aggregate:

   for (int i = 1; i <= N; i++) { sum[i] += sum[i - 1]; }

//This is an O(N) step.

4. find the location k where sum[k] is maximum.
5. Iterate the new intervals [ai, bi] and find the first one that contains position k (ie. ai <= k && k <= bi).

This interval [ai, bi] is a solution and the number of times it intersects all the other intervals is "sum[k] - 1" (not accounting for itself).

Answer 5

An alternative approach to interval trees that may be suitable if the ai,bi are small integers (e.g. perhaps they are 16bit numbers) is to:

1. Make an array A with N values where N is bigger than max(bi)
2. Clear all values in the array to 0
3. Loop over the intervals and change A[ai]:=A[ai]+1, A[bi+1]:=A[bi+1]-1
4. Set x=0
5. Loop over the array computing x:=x+A[j], and look for the largest value of x

The value of x at iteration j gives the number of intervals that intersect the point j, so finding the largest value gives the point which intersects the most intervals.

This takes O(N+n) cycles so is only useful if n>N for your application.

(Strictly speaking, this does not answer the question as this finds the point that intersects most. However, you should be able to extend this approach to find the interval that intersects most.)

Answer 6

You can do it in n.

[ smallest ai, largest bi ]

So..

varmin = interval[0]['begin']
varmax = interval[0]['end']
foreach( interval as rang ) {
  varmin = min( rang['begin'], varmin )
  varmax = max( rang['end'], varmax ) }
newrange = array('begin'=>varmin,'end'=>varmax)