Counting Overlaps of Integer Ranges

问题:

I've been stumped on this algorithm for quite a bit.

Say there are four ranges of integers. Each range has a Start and an End value.

Range A: 0,5
Range B: 4,12
Range C: 2,10
Range D: 8,14

From these values I would like to get a new set which counts of the number of the ranges that fall in a particular span of ints. Each of these would have Start, End and Count values, producing something like this:

(Start, End, Count)
0,1,1   (Only 1 range (A) falls between 0 and 1 inclusive)
2,3,2   (2 ranges (A,C))
4,5,3   (3 ranges (A,B,C))
6,7,2   (2 ranges (B,C))
8,10,3  (3 ranges (B,C,D))
11,12,2 (2 ranges (B,D))
13,14,1 (1 range (D))

Does that make sense? What's a good way to approach the algorithm?

回答1:

You can solve this in O(N ln N) time (for sorting) followed by the same amount of time for outputting results. If the number range is large, O(N ln N) is better than the O(M·N) time of the method suggested in a comment (where M = total range of numbers covered by the ranges).

Sort the N ranges into ascending order, keyed by Start value, say in array S. Initialize an empty priority queue P. Initialize a depth-count D to zero, and the current “reach” to R = S[0].Start.

While S[i].Start=R, push S[i].End on P and advance i and D. When S[i].Start>R, yield the tuple (R, p.top, D). Pop P to R and then decrease D by one and pop P while P.top==R.

Repeat the above paragraph while i<N.

回答2:

function checkOverlap(arr){
  var overlaps = {}, i, j;
  // match each item against all others BUT itself
  for( i=0; i < arr.length; i++ )
      for( j=0; j < arr.length; j++ )
          if( arr[i] !== arr[j] && arr[i][1] < arr[j][2] && arr[j][1] < arr[i][2] )
            overlaps[arr[i][0]] = 1;

  return Object.keys(overlaps);
}

Run it against an Array of ranges, for example:

[
  ["a", 10, 12], 
  ["b", 20, 30], 
  ["c", 29, 30], 
  ["d", 15, 95], 
  ["e", 195, 196]
];

Playgroud demo

回答3:

A range x intersects the input range y if:

x.End >= y.Start AND y.End >= x.Start

So, for a given input, just loop through your collection of ranges and see which satisfy the above condition.

If your given collection of ranges doesn't change very often, and your collection of ranges gets much larger than the 4 you stated in the problem description, then sort them first so that you can more efficiently search for the ranges that intersect your input, rather than looping through all of them.

If the given collection of ranges changes often, the sorting could be too expensive, and it would then be smarter to just loop through all of them each time.