在另一个区间内查找所有不重叠的区间

Question

我有一个区间数组，另一个区间定义为范围。目标是创建一个数组数组，其中包含不重叠但在定义范围内的所有间隔的起始和结束编号。

它的最初用途是，我有一个服务器，为数十万个对象提供服务，这些对象的时间戳相隔一秒。一个请求可以用任意两个时间戳发出，所以我需要存储服务器上查询到的对象，下次用两个不同的时间戳发出请求时，只查询丢失的对象。这个问题用小数字来简化问题。

输入：

const intervals = [
[3, 5],
[7, 9],
];
const range = [2, 11];

这种情况下的输出将是[[2, 3], [5, 7], [9, 11]]

间隔始终按开始日期排序，输入间隔中从不重叠，因为根据此答案，合并和排序是事先完成的https://stackoverflow.com/a/67717721/13585195

我已经设法为这个特定的案例找到了解决方案，但当试图涵盖其他案例时，问题就出现了，例如：

1. 输入：间隔：[[3, 5]];量程：[4, 8];输出：[[5, 8]]
2. 输入：间隔：[[7, 11]];范围：[2, 8];输出：[[2, 7]]
3. 输入：间隔：[[3, 5], [6, 8]];范围：[4, 7];输出：[[5, 6]]
4. 输入：间隔：[[5, 10], [15, 20], [25, 30]];范围：[0, 35];输出：[[0, 5], [10, 15], [20, 25], [30, 35]]

我现在的代码检查所需的范围是否已经在缓存中，以及它是否与缓存的日期部分重叠：

const partiallyCached = cachedDates.some(
(cachedDate) =>
range.start.getTime() <= cachedDate.end.getTime() &&
cachedDate.start.getTime() <= range.end.getTime()
);
if (partiallyCached) {
console.log("Partially cached, merging query");
const queryRange = functionToFindNonOverlappingIntervalsInRange(cachedDates, range);
const newCachedDates = mergeOverlappingDateRanges([...cachedDates, range]);
return {
cache: newCachedDates,
queryRange,
};
}

我还想知道我是否应该继续写if语句来缩小上面写的每个情况，并为每个情况写一个单独的函数，或者是否可以写一个函数来解决所有情况。

Answer 1

您可以获取range的起始值，检查间隔并构建一个新数组。

const
getInbetween = (intervals, range) => {
const
result = [];

let value = range[0],
index = 0;
while (value < range[1] && index < intervals.length) {
let [left, right] = intervals[index];
if (value < left) result.push([value, left]);
value = right;
index++;
}
if (value < range[1]) result.push([value, range[1]]);
return result;
};
console.log(getInbetween([[3, 5], [7, 9]], [2, 11]));
console.log(getInbetween([[3, 5], [7, 9]], [4, 11]));
console.log(getInbetween([[3, 5], [7, 9]], [4, 8]));

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

Answer 2

假设这是排序的，并且所有间隔都被合并，那么只有几种情况需要考虑。

1. 范围的开始位于第一个元素之前
2. 范围的起点与第一个元素相交
3. 范围的末尾与最后一个元素相交
4. 范围的末尾超过了最后一个元素
5. 元素位于范围的起点和终点

function getNonOverlappingIntervals(intervals, [rangeStart, rangeStop]) {
const output = [];
let prevStop = null;
const intervalsInRange = intervals.filter(([start, stop]) => {
if (rangeStart <= start && rangeStop >= stop) return true;
if (start < rangeStart && stop > rangeStart) return true;
if (start < rangeStop && stop > rangeStop) return true;
return false;
});
// check if rangeStart precedes first interval
if (intervalsInRange[0][0] > rangeStart) {
output.push([rangeStart, intervalsInRange[0][0]]);
prevStop = intervalsInRange[0][1];
} else if (intervalsInRange[0][0] < rangeStart) {
prevStop = intervalsInRange[0][1];
}
// iterate intervals and compare against last checked interval
if (intervalsInRange.length > 2) {
for (let i = 1; i < intervalsInRange.length; i++) {
output.push([prevStop, intervalsInRange[i][0]]);
prevStop = intervalsInRange[i][1];
}
}
// check if rangeStop exceeds last interval
if (intervalsInRange[intervalsInRange.length - 1][1] < rangeStop) {
output.push([intervalsInRange.at(-1)[1], rangeStop]);
}
return output;
}
console.log(getNonOverlappingIntervals([[3, 5],[7, 9]], [2, 11]));
console.log(getNonOverlappingIntervals([[3, 5]], [4, 8]));
console.log(getNonOverlappingIntervals([[7, 11]], [2, 8]));
console.log(getNonOverlappingIntervals([[3, 5], [6, 8]], [4, 7]));
console.log(getNonOverlappingIntervals([[5, 10], [15, 20], [25, 30]], [0, 35]));