首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何从具有重叠时间范围的原始优先级范围数据数组中计算具有不同优先级的时间槽数组?

问如何从具有重叠时间范围的原始优先级范围数据数组中计算具有不同优先级的时间槽数组?
EN

Stack Overflow用户
提问于 2022-04-01 16:28:28
回答 3查看 139关注 0票数 0

我有一组具有以下接口的数据

代码语言:javascript
复制
interface data {
  start: double
  end: double
  priority: number // (1 | 2 | 3)
}[]

作为输出,我希望看到开始和结束的优先级范围。重叠范围只包含最高优先级。

举例:

代码语言:javascript
复制
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}
]

输出将是

代码语言:javascript
复制
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},
]

如您所见,根据优先级将数据分组为多个范围,重叠包含最高优先级。

你能用任何语言解决这个问题吗?我不需要完整的运行代码解决方案。如果我对哪种算法、数据结构适合这类问题有任何指导,这将对我有很大的帮助。

EN

回答 3

Stack Overflow用户

发布于 2022-04-02 09:41:39

您可以使用一个排序时间数组(开始/结束)以及类型和优先级。

代码语言:javascript
复制
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

第一,数据准备。第二,构建节点。

​

代码语言:javascript
复制
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);
代码语言:javascript
复制
.as-console-wrapper { max-height: 100% !important; top: 0; }

​

票数 0
EN

Stack Overflow用户

发布于 2022-04-02 20:42:03

一种可能的办法应首先使现有的优先范围数据正常化,例如始终确保统一的时间顺序和合并的、封闭的或重叠的同等优先范围。

对于这类规范化数据的定时优先级时隙的创建任务更容易实现。

这两个任务,规范化和创建任务,都利用了Array.prototype.reduce和Array.prototype.sort。

之前提供了一个图表,它在执行时间槽创建任务前不久显示了首选排序。由于她同时删除了她的答案,我再提供一次,虽然略有改变。

排序是基于按升序排序的优先级范围项的start值(无论项目的priority)。

代码语言:javascript
复制
priority  time
--------  -----------------------------------------
      1    1.2                      9.2
      2         2.1            7.2
      3              3.5  5.9
      2                                  9.7  10.8

​

代码语言:javascript
复制
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 });
代码语言:javascript
复制
.as-console-wrapper { min-height: 100%!important; top: 0; }

​

备注

上述实现很可能没有涵盖任何可能的边缘情况。对于后者,OP必须提供特定的优先级范围数据场景。

票数 0
EN

Stack Overflow用户

发布于 2022-04-06 18:03:23

我认为,通常更容易从一系列转换的角度来考虑这些问题,每个转换本身都很简单,但它们一起可以执行任意复杂的任务。

下面是我们如何改变这个问题的草图:

从输入的numerically

  • Create start和end值中提取出所有唯一的start和end值--这些值为每个范围的每个连续对

  • 的起始值和结束值,创建具有start和end值的对象以及与其重叠的原始事件&H 212/code>H 113删除所有不包含事件H 214/代码>H 115/代码>的范围,为每个范围提取最大的优先级并附加最大的H 216H 117将连续的范围与相同的优先级结合在一起。H 218F 219/>代码

这听起来像是很多步骤,但是当它们都很简单(可以说是最后一个步骤除外)时,代码就不算太糟了。下面是一个JavaScript实现:

​

代码语言:javascript
复制
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))
代码语言:javascript
复制
.as-console-wrapper {max-height: 100% !important; top: 0}

​

我们通过flatMapping启动一个函数,从项中提取开始时间和结束时间,然后用[... new Set (/* ... */)]进行包装,以选择唯一的值。

这将产生如下结果:

代码语言:javascript
复制
[1.2, 8.1, 9.2, 2.1, 7.2, 3.5, 5.9, 9.7, 10.8]

我们想得到的

代码语言:javascript
复制
[1.2, 2.1, 3.5, 5.9, 7.2, 8.1, 9.2, 9.7, 10.8]

我们把这些变成成对,产生:

代码语言:javascript
复制
[[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]]

现在我们把这些变成对象,看起来像这样:

代码语言:javascript
复制
[
  {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}]}
]

然后,尽管示例没有说明这一点,但我们可能会有一些空范围,没有事件。由于我们的输出需要有优先级,而这些优先级不需要,所以我们使用filter删除它们,在本例中返回相同的结构:

代码语言:javascript
复制
[
  {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}]}
]

现在,通过提取每个事件的优先级并选择最高的一个,我们创建了最终格式的元素:

代码语言:javascript
复制
[
  {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}
]

这里还有一步,这是最复杂的一步。我们需要结合具有相同优先级的相邻事件。在这里,7.2 - 8.1: 1和8.1 - 9.2: 1不应该保持分离。我们通过将事件折叠到一个新数组中来做到这一点,通常只是附加到它之后,但是,当前一个事件与当前的事件(end == e.start)相邻,并且它们共享相同的优先级时,我们用一个新的数组替换前一个数组,这个新数组从上一个值的start开始,以当前值的end结束。

最后,我们最后会:

代码语言:javascript
复制
[
  {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}
]

这种风格可能不像任何形式的“一条龙”,但它更简单,更容易改变,更容易被分解成可重复使用的部分。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/71710129

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档