How to get the number of collisions in overlapping sets?

Question

For a project which I am doing, I have a list of sets in the form of

[ [start, end] ]

For example

[{1, 3} {2, 4} {5, 9} {6, 8} {7, 8}]

The array is in sorted form.

I want to find the number of overlapping collisions. For example from the example dataset.

The result I want is like the following.

 Interval | Collisions
----------------------
 {7,8}    | 3
 {2,3}    | 2
 {6,7}    | 2
 {1,2}    | 1
 {3,4}    | 1
 {5,6}    | 1
 {8,9}    | 1

What is the ideal way to achieve it ?

Not exactly a duplicate, but perhaps close enough: [Finding (number of) overlaps in a list of time ranges](http://stackoverflow.com/questions/2244964/finding-number-of-overlaps-in-a-list-of-time-ranges). — Bernhard Barker, May 14 '17 at 21:37

score 3 · Accepted Answer · answered May 14 '17 at 21:30

You can translate each list-element into two elements, one representing just the start and one representing just the end. Then, sort the result, giving you this:

start at 1
start at 2
end at 3
end at 4
start at 5
start at 6
start at 7
end at 8
end at 8
end at 9

Now you can iterate through the list, keeping track of how many sets you've entered and exited at each point.

How to get the number of collisions in overlapping sets?

1 Answers1