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 i

Solution 1:

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);

Solution 2:

If the order of the segments in the output does not matter, then I think we can do this relatively simply:

const aperture = (n) => (xs) => 
  xs .length < n ? [] : [xs .slice (0, n), ... aperture (n) (xs .slice (1))]

const partition = (input) => 
  aperture (2) (
    [... new Set ([... input] .flatMap (({start, end}) => [start, end]))] 
      .sort ((a, b) => a - b)
  ) .map (([start, end]) => ({start, end}))


console .log ('example 1',
  partition ([{start: 4.5, end: 9}, {start: 3.9, end: 9.5}, {start: 2.5, end: 11.5}])
)

console .log ('example 2',
  partition ([{start: 4.5, end: 5.5}, {start: 7.5, end: 8.5}, {start: 3.5, end: 9.5}])
)

.as-console-wrapper {max-height: 100% !important; top: 0}

aperture essentially moves a sliding window of length n over an array of values, yielding a number of smaller arrays. For instance,

aperture (3) ([8, 6, 7, 5, 3, 0, 9]) 
//=> [[8, 6, 7], [6, 7, 5], [7, 5, 3], [5, 3, 0], [3, 0, 9]]

Our partition function takes all the start and end indices, flattens them out into a single array, removes duplicates (through [... new Set (<elements>)]), sorts them numerically, then uses aperture to group them into pairs, and then turns those pairs back into {start, end} objects.

If this is what you're looking for, none of the layering discussion in the question and comments is particularly relevant.

Update

It looks as though you are looking to track these by level. Here's a technique that will do this, probably less efficiently than the technique by trincot, but to my mind somewhat more understandably:

const subtractSeg = ({start: a, end: b}, {start: c, end: d}) => 
  c < a
    ? d < a ? [{start: a, end: b}] : d < b ? [{start: d, end: b}] : []
  : c < b
    ? d < b ? [{start: a, end: c}, {start: d, end: b}] : [{start: a, end: c}]
  : [{start: a, end: b}]

const subtractAllSegs = (seg, segs) =>
  segs .reduce ((a, s) => a .flatMap ((t) => subtractSeg (t, s)), [seg]) 
       .filter (({start, end}) => start < end)

const partition = ([seg, ...segs]) => 
  segs .reduce ((a, s) => [...a, subtractAllSegs(s, a .flat ())], [[seg]])

console .log ('example 1',
  partition ([{start: 4.5, end: 9}, {start: 3.9, end: 9.5}, {start: 2.5, end: 11.5}])
)

console .log ('example 2',
  partition ([{start: 4.5, end: 5.5}, {start: 7.5, end: 8.5}, {start: 3.5, end: 9.5}])
)

.as-console-wrapper {max-height: 100% !important; top: 0}

The new partition function is built atop one which subtracts a number of segments from one segment, which in turn is built atop one which subtracts one segment from another. The .reduce call in partition keeps each level distinct.

This pairs the new segments with the original simply through shared indices. We could clearly zip these together if you need a more explicit mapping.

Deeper Explanation

A comment from the OP found this answer difficult to comprehend. Here's an attempt at a more complete explanation.

First we have the function subtractSeg, which subtracts the contents of one segment from another, leaving zero, one, or two segments in its place. The function is built out of nested conditional expressions (ternaries) but is in essence just a way to present this diagram in a function:

                    Subtracting (c, d) from (a, b)
                    ==============================

----(---)---[===]----  :: c < a && d < a             :: [(a, b)]
    c   d   a   b

----(---[---)===]----  :: c < a && d >= a && d < b   :: [(d, b)]
    c   a   d   b

----(---[---]---)----  :: c < a && d >= a && d >= b  :: []
    c   a   b   d

----[===(---)===]----  :: c >= a && c < b && d < b   :: [(a, c), (d, b)]
    a   c   d   b
      
----[===(---]---)----  :: c >= a c < b && d < b      :: [(a, c)]
    a   c   b   d
      
----[===]---(---)----  :: c >= a c >= b              :: [(a, b)]
    a   b   c   d

For this problem, we are simply not worrying about inclusion or exclusion of endpoints, or this would grow additional layers. Because we have one case (a < c < d < b) which yields multiple segments, we wrap all the results in arrays.

Then we write a function to subtract all of a collection of segments from a given segment. We do this using reduce. The internal flatMap is because as seen above, we will sometimes create multiple segments when subtracting one from another. In this call:

subtractAllSegs ({start: 5, end: 23}, [
  {start: 12, end: 14},
  {start: 2, end: 4},
  {start: 9, end: 15},
  {start: 16, end: 18}
])

we first perform subtractSeg ({start: 5, end: 23}, {start: 12, end: 14}), yielding [{start: 5, end: 12}, {start: 14, end: 23}]. Then from each of those, we subtract {start: 2, end: 4}, which overlaps neither of them, and so gives back the same result. Then we subtract {start: 9, end: 15}, which happens to overlap both, and yields [{start: 5, end: 9}, {start: 15, end: 23}]. Finally we subtract {start: 16, end: 18} from both. It does not overlap the first one, but splits the second in two, yielding [{start: 5, end: 9}, {start: 15, end: 16}, {start: 18, end: 23}].

The .filter call simply removes potential detritus of empty segments such as {start: 9, end: 9}.

Finally, our partition function looks like this:

const partition = ([seg, ...segs]) => 
  segs .reduce ((a, s) => [...a, subtractAllSegs(s, a .flat ())], [[seg]])

We destructure the input array of segments, so that we can deal with the topmost level separately. We wrap that first layer in a double layer of arrays, and pass it as an initial value into a fold on the remainder. At each step we take the current segment and subtract from it all the values from every levels above it (combined into a single array by the call to .flat()), and push the results as a new subarray of the accumulator.

For example, in this call:

  partition ([{start: 4.5, end: 5.5}, {start: 7.5, end: 8.5}, {start: 3.5, end: 9.5}])

We start with this initial value:

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

Then we add a second layer by subtracting everything in that top layer from {start: 7.5, end: 8.5}. There is only one thing above it and that doesn't overlap, so our new accumulator looks like this:

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

Now we subtract everything in those two layers from {start: 2.5, end: 9.5}, yielding three segments, and a final array that looks like this:

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

The main point of a solution like this is that we break the problem down into manageable chunks. We write one function to subtract a segment from another. We use this along with .reduce, .flatMap and .filter to subtract a number of segments from one, and then using the new function with .reduce and .flat, we can write simple code to transform your original data. None of these function is particularly complex. subtractSeg is a little obnoxious as we need to test for six different cases, but it still is simple, and the other two are even simpler.