How to calculate an array of timed slots with varying priority from an array of raw priority-range d-CodePudding

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

CodePudding user response：

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.

CodePudding user response：

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:

separate all tata into object with start and end time along with type (start/end) and priority,
sort by time and type,
group into array with same amount of start and end objects, like bracket balancing.

Second, building nodes:

update end, if object exists.
check type and if 'start'
- if nothing has happened continue,
- add a new object to the result set
- if object exists (the former object now), add the last priority to priorities.
else
- if priorities has a length, add a new object with priority form the last priorities,
finally assign type to lastType,
outside of the group add temporary collected nodes to result set.

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 }],
    groups = data
        .reduce((r, { start, end, priority }) => {
            r.push({ time: start, type: 'start', priority });
            r.push({ time: end, type: 'end', priority });
            return r;
        }, [])
        .sort((a, b) => a.time - b.time || (b.type === 'start') - (a.type === 'start'))
        .reduce((open => (r, o) => {
            if (!open) r.push([]);
            open  = o.type === 'start' || -1;
            r[r.length - 1].push(o);
            return r;
        })(0), []),
    result = [];

for (const points of groups) {
    const
        temp = [],
        priorities = [];

    let lastType;

    for (const { time, type, priority } of points) {
        const level = temp[temp.length - 1];
        if (level) level.end = time;
        if (type === 'start') {
            if (lastType === type && level?.priority === priority) continue;
            temp.push({ start: time, end: time, priority });
            if (level) priorities.push(level.priority);
        } else {
            if (priorities.length) temp.push({ start: time, end: time, priority: priorities.pop() });
        }
        lastType = type;
    }
    result.push(...temp);
}

console.log(result);
console.log(groups);

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