How to calculate an array of timed slots with varying priority from an array of raw priority-range data-items with overlapping time-ranges?

Question

I have a set of data that has the following interface

interface data {
  start: double
  end: double
  priority: number // (1 | 2 | 3)
}[]

As an output, I want to see the range of priority over the start and end. The overlapped range will contain only the highest priority

Example given:

data = [
  { start: 1.2, end: 8.1, priority: 1},
  { start: 1.2, end: 9.2, priority: 1},
  { start: 2.1, end: 7.2, priority: 2},
  { start: 3.5, end: 5.9, priority: 3},    
  { start: 9.7, end: 10.8, priority: 2}
]

The output will be

const result = [
  { start: 1.2, end: 2.1, priority: 1},
  { start: 2.1, end: 3.5, priority: 2},
  { start: 3.5, end: 5.9, priority: 3},
  { start: 5.9, end: 7.2, priority: 2},
  { start: 7.2, end: 9.2, priority: 1},
  { start: 9.7, end: 10.8, priority: 2},
]

As you can see, the data is grouped into multiple ranges based on priority, and overlapped contains the highest priority.

Could you please solve the problem in any language? I don't need full running code solution. If I get any direction on what algorithm, data structure is suitable for this type of problem, this would be much helpful to me

Answer 1

A possible approach should start with normalizing the available priority range data in order to e.g. always ensure both a unified chronological order and merged enclosed or overlapping ranges of equal priority.

It is easier to implement the creation task for timed priority slots for such normalized data.

Both tasks, the normalizing and the creating one, make use of Array.prototype.reduce and Array.prototype.sort.

Nina Scholz earlier provided a diagram which did show the preferred sorting shortly before the timed-slot creation-task executes. Since she meanwhile did delete her answer, I provide it again, slightly changed though.

The sorting is based on the priority range items' start value (regardless of an item's priority) in ascending order.

priority  time
--------  -----------------------------------------
      1    1.2                      9.2
      2         2.1            7.2
      3              3.5  5.9
      2                                  9.7  10.8

function getNormalizedPriorityRangeData(rangeList) {
  function orderByTopMostPriorityRangeCoverage(a, b) {
    return  (
      (a.priority - b.priority) ||
      (a.start - b.start) ||
      (b.end - a.end)
    );
  }
  function mergeRangesOfSamePriority(result, priorityRange) {
    // const recentPriorityRange = result.at(-1) ?? null;
    const recentPriorityRange = result.slice(-1)[0] ?? null;

    if (
      (recentPriorityRange !== null) &&
      (recentPriorityRange.priority === priorityRange.priority)
    ) {
      const {
        start = 0, end = 0, priority = 0,
      } = recentPriorityRange;

      const {
        start: currentStart = 0,
        end: currentEnd = 0,
        priority: currentPriority = 0,
      } = priorityRange;

      if (currentStart > end) {

        result.push(priorityRange);
      } else if (
        (currentStart >= start)
        && (currentEnd > end)
      ) {
        recentPriorityRange.end = currentEnd;
      }
    } else {
      result.push(priorityRange);
    }
    return result;
  };

  return [...rangeList]
    .sort(orderByTopMostPriorityRangeCoverage)
    .reduce(mergeRangesOfSamePriority, []);
}

function getTimedPrioritySlots(rangeList) {
  function orderByTimeSlotAndPriorityAscending(a, b) {
    return  (
      (a.start - b.start) ||
      (a.priority - b.priority)
    );
  }
  function createAndCollectTimedSlot(result, priorityRange, idx, arr) {
    const previousRange = arr[idx - 1];
    const nextRange = arr[idx + 1];

    const { start, end, priority } = priorityRange;

    const {
      start: nextStart,
      end: nextEnd,
      priority: nextPriority,
    } = (nextRange ?? {});

    const {
      start: previousStart,
      end: previousEnd,
      priority: previousPriority,
    } = (previousRange ?? {});

    if (nextRange) {
      if ((nextStart > start) && (nextStart < end)) {

        result.push({ start, end: nextStart, priority });

      } else if (end < nextStart) {

        result.push({ start, end, priority }); // clone;
      }
    }
    if (previousRange) {
      if ((previousEnd < end) && (previousEnd > start)) {

        result.push({
          start: previousEnd,
          end,
          priority,
        });
      } else if (end < previousEnd) {

        result.push({
          start: end,
          end: previousEnd,
          priority: previousPriority,
        });
      } else if (previousEnd < start) {

        result.push({ start, end, priority }); // clone;
      }
    }
    return result;
  }

  return getNormalizedPriorityRangeData(rangeList)
    .sort(orderByTimeSlotAndPriorityAscending)
    .reduce(createAndCollectTimedSlot, [])
    .sort((a, b) => a.start - b.start);
}

const data = [
  { start: 1.2, end: 8.1, priority: 1 },
  { start: 1.2, end: 9.2, priority: 1 },
  { start: 2.1, end: 7.2, priority: 2 },
  { start: 3.5, end: 5.9, priority: 3 },    
  { start: 9.7, end: 10.8, priority: 2 },
];
const normalizedData = getNormalizedPriorityRangeData(data);

const timedPrioritySlots = getTimedPrioritySlots(data);

console.log({ data, normalizedData, timedPrioritySlots });

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

Note

The above implementation most probably does not cover any possible edge case. For the latter the OP has to provide specific priority-range data-scenarios.

Answer 2

You could take an array of sorted times (start/end) along with type and priority.

priority  time
--------  ----------------------------------------------
      1    1.2                      8.1      |
      1    1.2                           9.2 | 
      2         2.1            7.2           |
      3              3.5  5.9                |
      2                                      | 9.7  10.8  
--------  ----------------------------------------------
parts          1    2    3     4       5     |     1
priority       1    2    3     2       1     |     2

First, data preparation. Second, building nodes.

const
    data = [{ start: 1.2, end: 8.1, priority: 1 }, { start: 1.2, end: 9.2, priority: 1 }, { start: 2.1, end: 7.2, priority: 2 }, { start: 3.5, end: 5.9, priority: 3 }, { start: 9.7, end: 10.8, priority: 2 }],
    points = data
        .flatMap(({ start, end, priority }) => [
            { time: start, type: 'start', priority },
            { time: end, type: 'end', priority }
        ])
        .sort((a, b) => a.time - b.time || (b.type === 'start') - (a.type === 'start')),
    result = [],
    priorities = [];

let open = 0,
    lastType,
    update;

for (const { time, type, priority } of points) {
    const level = result[result.length - 1];

    if (!open) {
        update = false;
        priorities.length = 0;
    }
    open += type === 'start' || -1;

    if (update) level.end = time;
    if (type === 'start') {
        if (lastType === 'start' && level?.priority === priority) continue;
        result.push({ start: time, end: time, priority });
        if (update) priorities.push(level.priority);
        update = true;
    } else {
        if (priorities.length) result.push({ start: time, end: time, priority: priorities.pop() });
    }
    lastType = type;
}

console.log(result);
console.log(points);

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

Answer 3

I think it's often easier to think about such problems in terms of a sequence of transformations, each one simple in its own right but which together can do arbitrarily complex tasks.

So here's a sketch of how we might transform this:

• Extract all the unique start and end values from our input
• Sort these values numerically
• Create simple array ranges with start and end values for each consecutive pair
• For each range, create objects with start and end values and the original events which overlap it
• Remove all the ranges which contain no events
• For each range, extract the priorities and attach the largest one
• Combine consecutive ranges with the same priority.

This sounds like a lot of steps, but when they're all simple (except, arguably the last one) the code is not too bad. Here's a JavaScript implementation:

const normalizeRanges = (data) =>
  [... new Set (data .flatMap (({start, end}) => [start, end]))] 
    .sort ((a, b) => a - b)
    .reduce ((a, x, i, xs) => i == 0 ? [] : [...a, [xs [i - 1], x]], [])  
    .map (([a, b]) => ({start: a, end: b, events: data .filter (({start, end}) => start < b && end > a)}))
    .filter (({events}) => events .length > 0)
    .map (({start, end, events}) => ({start, end, priority: Math .max (...events .map (e => e.priority))}))
    .reduce (
      (a, e, i, _, {start, end, priority} = i > 0 && a .at (-1)) => 
        i == 0 ? [e] : priority == e.priority && end == e.start ? [...a .slice (0, -1), {start, end: e.end, priority}] : [...a, e],
      []
    )

const data = [{start: 1.2, end: 8.1, priority: 1}, {start: 1.2, end: 9.2, priority: 1}, {start: 2.1, end: 7.2, priority: 2}, {start: 3.5, end: 5.9, priority: 3}, {start: 9.7, end: 10.8, priority: 2}]

console .log (normalizeRanges (data))
    

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

We start by flatMapping a function to extract start and end times from the items, and wrap that up with [... new Set (/* ... */)] to choose unique values.

That will yield something like:

[1.2, 8.1, 9.2, 2.1, 7.2, 3.5, 5.9, 9.7, 10.8]

which we sort to get

[1.2, 2.1, 3.5, 5.9, 7.2, 8.1, 9.2, 9.7, 10.8]

We turn these into pairs, yielding:

[[1.2, 2.1], [2.1, 3.5], [3.5, 5.9], [5.9, 7.2], [7.2, 8.1], [8.1, 9.2], [9.2, 9.7], [9.7, 10.8]]

Now we turn these into objects, that look like this:

[
  {start: 1.2, end: 2.1, events: [{start: 1.2, end: 8.1, priority: 1}, {start: 1.2, end: 9.2, priority: 1}]}, 
  //...
  {start: 9.7, end: 10.8, events: [{start: 9.7, end: 10.8, priority: 2}]}
]

Then, although the sample doesn't demonstrate this, it's possible that we would have some empty ranges, with no events. Since our output needs to have priorities, and these do not, we remove them with filter, returning in this case, the same structure:

[
  {start: 1.2, end: 2.1, events: [{start: 1.2, end: 8.1, priority: 1}, {start: 1.2, end: 9.2, priority: 1}]}, 
  //...
  {start: 9.7, end: 10.8, events: [{start: 9.7, end: 10.8, priority: 2}]}
]

Now we create elements of our final format, by extracting the priorities for each event, and choosing the highest one:

[
  {start: 1.2, end: 2.1, priority: 1}
  {start: 2.1, end: 3.5, priority: 2}
  {start: 3.5, end: 5.9, priority: 3}
  {start: 5.9, end: 7.2, priority: 2}
  {start: 7.2, end: 8.1, priority: 1}
  {start: 8.1, end: 9.2, priority: 1}
  {start: 9.7, end: 10.8, priority: 2}
]

There is one more step here, and it's the most complex one. We need to combine abutting events that have the same priority. Here 7.2 - 8.1: 1 and 8.1 - 9.2: 1 should not remain separate. We do this by folding the events down to a new array, just appending to it normally, but, when the previous event abuts the current one (end == e.start) and they share the same priority, we replace the previous one with a new one that starts at the previous value's start and ends at the current value's end.

And finally, we'll end up with:

[
  {start: 1.2, end: 2.1, priority: 1}
  {start: 2.1, end: 3.5, priority: 2}
  {start: 3.5, end: 5.9, priority: 3}
  {start: 5.9, end: 7.2, priority: 2}
  {start: 7.2, end: 9.2, priority: 1}  // two for the price of one!
  {start: 9.7, end: 10.8, priority: 2}
]

Such a style is likely less performant that any sort of do-it-all-in-one-loop approach, but it is simpler, easier to change, easier to break into reusable pieces.