我有一组具有以下接口的数据
interface data {
start: double
end: double
priority: number // (1 | 2 | 3)
}[]作为输出,我希望看到开始和结束的优先级范围。重叠范围只包含最高优先级。
举例:
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 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},
]如您所见,根据优先级将数据分组为多个范围,重叠包含最高优先级。
你能用任何语言解决这个问题吗?我不需要完整的运行代码解决方案。如果我对哪种算法、数据结构适合这类问题有任何指导,这将对我有很大的帮助。
发布于 2022-04-02 09:41:39
您可以使用一个排序时间数组(开始/结束)以及类型和优先级。
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第一,数据准备。第二,构建节点。
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; }
发布于 2022-04-02 20:42:03
一种可能的办法应首先使现有的优先范围数据正常化,例如始终确保统一的时间顺序和合并的、封闭的或重叠的同等优先范围。
对于这类规范化数据的定时优先级时隙的创建任务更容易实现。
这两个任务,规范化和创建任务,都利用了Array.prototype.reduce和Array.prototype.sort。
之前提供了一个图表,它在执行时间槽创建任务前不久显示了首选排序。由于她同时删除了她的答案,我再提供一次,虽然略有改变。
排序是基于按升序排序的优先级范围项的start值(无论项目的priority)。
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; }
备注
上述实现很可能没有涵盖任何可能的边缘情况。对于后者,OP必须提供特定的优先级范围数据场景。
发布于 2022-04-06 18:03:23
我认为,通常更容易从一系列转换的角度来考虑这些问题,每个转换本身都很简单,但它们一起可以执行任意复杂的任务。
下面是我们如何改变这个问题的草图:
从输入的numerically
start和end值中提取出所有唯一的start和end值--这些值为每个范围的每个连续对
start和end值的对象以及与其重叠的原始事件&H 212/code>H 113删除所有不包含事件H 214/代码>H 115/代码>的范围,为每个范围提取最大的优先级并附加最大的H 216H 117将连续的范围与相同的优先级结合在一起。H 218F 219/>代码这听起来像是很多步骤,但是当它们都很简单(可以说是最后一个步骤除外)时,代码就不算太糟了。下面是一个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)).as-console-wrapper {max-height: 100% !important; top: 0}
我们通过flatMapping启动一个函数,从项中提取开始时间和结束时间,然后用[... new Set (/* ... */)]进行包装,以选择唯一的值。
这将产生如下结果:
[1.2, 8.1, 9.2, 2.1, 7.2, 3.5, 5.9, 9.7, 10.8]我们想得到的
[1.2, 2.1, 3.5, 5.9, 7.2, 8.1, 9.2, 9.7, 10.8]我们把这些变成成对,产生:
[[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]]现在我们把这些变成对象,看起来像这样:
[
{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删除它们,在本例中返回相同的结构:
[
{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}]}
]现在,通过提取每个事件的优先级并选择最高的一个,我们创建了最终格式的元素:
[
{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结束。
最后,我们最后会:
[
{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}
]这种风格可能不像任何形式的“一条龙”,但它更简单,更容易改变,更容易被分解成可重复使用的部分。
https://stackoverflow.com/questions/71710129
复制相似问题