# Split overlapping ranges into all unique ranges

I am trying to split a dynamic number of ranges with associated attributes, so that whenever 2 or more ranges overlap, the overlapping section(s) are split into unique ranges with the combination of all overlapping attributes. To be more specific, say I have

``````1-10 - attributes a
7-12 - attributes b
9-15 - attributes c
``````

I want to make this

``````1-6 - attributes a
7-8 - attributes a, b
9 - 10 - attributes a,b,c
11-12 - attributes b,c
13-15 - attributes c
``````

It actually boils down to applying styling to ranges in Open Office XML, but I believe the underlying logic could be solved for any scenario. Thanks for any advice on how to approach this. I'm going to be using node/javascript, but I think any language demonstrating the method would suffice.

Here is what I would do:

• Make an array of triplets (n, attr, e), with two elements per each given interval. One encodes the starting point, and will have e=false, the other encodes the ending point, and will have e=true.

In your example, you will have [(1,a,false), (10,a,true),(7,b,false), (12,b,true),(9,c,false), (15,c,true)].

• Sort this array on n and e lexicographically (taking false < true)

Now you have [(1,a,false), (7,b,false), (9,c,false), (10,a,true), (12,b,true), (15,c,true)]

• Now make one pass through the sorted array, keeping the "current" set of attributes S (which, at the beginning, is empty). In each step, update S and then output the interval from the two consecutive elements in the array (adjusting the endpoints by 1 if necessary, and skipping empty intervals). In other words, if you have a pair of consecutive triplets (n, a, e) and (m, b, f), the step is:
• If e=false, add a to S. If e=true, take away a from S.
• Define n'=n if e=false or n'=n+1 if e=true
• Define m'=m-1 if f=false or m'=m if f=true
• If n' <= m', output (n',m',S), otherwise output nothing.

In our example, the output will be [(1,6, {a}), (7,8, {a,b}), (9,10, {a,b,c}), (11,12, {b,c}), (13,15, {c})].

• This answer doesn't take account of gaps (gaps should not appear in output), so I refined it: * If e=false, add a to S. If e=true, take away a from S. * Define n'=n if e=false or n'=n+1 if e=true * Define m'=m-1 if f=false or m'=m if f=true * If n' <= m' and (e and not f) = false, output (n',m',S), otherwise output nothing. – silentman.it Aug 23 '18 at 12:19
• for what it's worth I don't think this additional condition to exclude gaps is working correctly. – Michael Apr 24 '19 at 23:32
• – Michael Apr 24 '19 at 23:45