Given a list of ranges some with higher priority than others determine the non-overlapping segments

The title of the question may not be completely clear (probably isn’t) so let me give an example.

NOTE: The algorithmic approach is described towards the end of the question, but it needs the following examples to be understandable.

Let’s say we have 3 ranges:

[
  {start: 4.5, end: 9}, // a
  {start: 3.9, end: 9.5}, // b
  {start: 2.5, end: 11.5} // c
]

These ranges can be visualized like a video editor as follows:

        [  a  ]

      [    b    ]

    [      c       ]

I would like to find all the non-overlapping sections of for each range. In the above case I would like an output of:

c: [{start: 2.5, end: 3.9}, {start: 9.5, end: 11.5}] -> This is from the left edge of c to the left edge of b & the right edge of b to the right edge of c

b: [{start: 3.9, end: 4.5}, {start: 9, end: 9.5}] -> This is from the left edge of b to the left edge of a & the right edge of a to the right edge of b

a: [{start: 4.5, end: 9}] -> there is no overlap since a is the "highest" layer

This however is just one case, there could be any amount of layers on a given row, take the following for example:

[
  {start: 4.5, end: 5.5}, // a1
  {start: 7.5, end: 8.5}, // a2
  {start: 3.5, end: 9.5} // b
]

Visualized as

   [ a1 ]    [ a2 ]

 [         b         ]

The output should account for the ranges from the left of b to the left of a1, the gap between a1 and a2, and the right edge of a2 to the right edge of b:

a1: [{start: 4.5, end: 5.5}]

a2: [{start: 7.5, end: 8.5}]

b: [{start: 3.5, end: 4.5}, {start: 5.5, end: 7.5}, {start: 8.5, end: 9.5}]

Or another example just to drive the point home

[    a      ]

    [       b       ]

 [       c       ]

c should have no output since there is no point at which there isn’t any other layer above it and b should have an output of the right side of a to the right side of b.

I guess another way to phrase this would be, imagine that there’s a light shining straight down, I would like the ranges where the light would hit on each layer. Since a is at the top there would be no blocking, b would receive some light, and c would receive none.

Preferably an answer in JavaScript, but even pseudo-code would do.

Answer

I’ll assume that the height of each range is unique and is defined by the opposite of the index, so that the last range in the input is the lowest and the first range in the input is at the top.

You could extract the start and end properties of each range and create a new array where these are “events” that either start a range or end it.

Sort this new array so you can visit each event in non-decreasing order.

Then maintain for each level what its current “open” state is:

  • either true, when a “start” event was processed but not yet the corresponding “end” event.
  • or false, in all other cases (no “start” event was processed, or the “end” event was processed).

This way you have all you need to build the desired result. I assume that the result will be an array of sub-arrays. The outer array will have just as many elements as the input, so that the input/output matches by index. The inner subarrays will list the ranges that belong to the same level.

function partition(segments) {
    // split ranges into events and sort them
    let events = segments.flatMap(({start, end}, level) => 
        [{ value: start, level, isOpen: true  },
         { value: end,   level, isOpen: false }]
    ).sort((a, b) => a.value - b.value);
    
    let result = segments.map(() => []);
    let { value: start, level: currentLevel } = events[0];
    let levelIsOpen = Array(segments.length).fill(false);
    levelIsOpen[currentLevel] = true;
    for (let { value, level, isOpen } of events.slice(1)) {
        levelIsOpen[level] = isOpen;
        if (level > currentLevel) continue; // event is not visible
        if (value > start && currentLevel < segments.length) { // only add non-empty ranges
            result[Math.max(currentLevel, level)].push({ start, end: value });
        }
        // Adapt current level (i.e. max visibility of levels)
        if (isOpen) currentLevel = level;
        while (levelIsOpen[currentLevel] === false) currentLevel++;
        start = value;
    }
    return result;
}

// demo
let segments = [
  {start: 4.5, end: 9},
  {start: 3.9, end: 9.5},
  {start: 2.5, end: 11.5}
];

let result = partition(segments);
console.log(result);