Announcing Stack Overflow Documentation



Sign up and start helping → Learn more about Documentation →

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.

share|improve this question
up vote 10 down vote accepted

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.

share|improve this answer
how are you sorting the array , i mean on the basis of what? can you show me by sorting 3 intervals for example take (1,2), (1,3) , (2,4) – Peter Mar 23 '12 at 8:26
If (a1,b1),(a2,b2),(a3,b3) = (1,2),(1,3),(2,4), then the sorted order is a2,a1,b1,a3,b2,b3. – PengOne Mar 23 '12 at 17:58
@PengOne "Mark each point as an a or a b (maybe keep a binary array of length 2n to do this)." On what basis do I mark a point ? – Geek Aug 26 '12 at 13:37
@PengOne The algorithm does not work for (1,3) (2,3.5) (2.5,3) (3.5,4) Also for (1,6) (2,3) (4,5) in this case the answer should be 1,6 but it is not – Peter Jan 5 '13 at 15:07
A better answer is here. – itsadok Jul 17 '14 at 3:08

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).

share|improve this answer

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.)

share|improve this answer

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.


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;
share|improve this answer

You can do it in n.

[ smallest ai, largest bi ]


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)
share|improve this answer
I think you should rather pick one of the ranges instead of defining a new range. – Gumbo Mar 12 '12 at 18:24
Why? He said "find the range", not "expand a range to include the new range". – DanRedux Mar 12 '12 at 18:34

Your Answer


