Counting Overlaps of Integer Ranges

Question

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?

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

Answer 2

const ranges = {
  A: [10, 12],
  B: [20, 30],
  C: [29, 31],
  D: [15, 95],
  E: [195, 196]
};

let overlaps = {},
    keys = Object.keys(ranges),
    values = Object.values(ranges),
    i, j;

for (i = 0; i < values.length; i++)
  for (j = 0; j < values.length; j++)
    if (keys[i] !== keys[j] &&           // skip same item
        values[i][0] < values[j][1] &&   // overlap check
        values[j][0] < values[i][1])     // overlap check
      overlaps[keys[i]] = 1;

console.log( Object.keys(overlaps) )