Quickly get coverage of each position in arrary

Question

It is a short problem, There is a list of intervals, for example:

[1,4],[2,5],[3,6]

I want to get the coverage, which means number of intervals that overlap on the current position of each position from smallest to largest number (1 to 6)(like a line sweep from 1 to 6 and get number of hits at each position), the result should be:

[1,2,3,3,2,1]

Is there any way to quickly find this out, I can iterate all positions and see if it is in each interval, but that is too slow, is there any way to get this quick? Because in practice there can be millions of intervals, I am thinking of representing each interval as bit arrary but still cannot figure out, if anyone has idea, please let me know Thanks!

Answer 1

You could map your set of intervals in a set of number pairs (time; delta)

[1,4],[2,5],[3,6]

becomes

(1;+1), (4;-1), (2;+1), (5;-1), (3;+1), (6;-1)

Then sort the set of pairs in ascending order of their time entries

(1;+1), (2;+1), (3;+1), (4;-1), (5;-1), (6;-1)

Finally, go through this list and increment/decrement the coverage count, initialized at zero:

(1;1), (2;2), (3;3), (4;2), (5;1), (6;0)