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

Question

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

这个的最初用途是我有一个服务于数十万个对象的服务器，这些对象的时间戳彼此相隔一秒。可以使用任意两个时间戳发出请求，因此我需要从服务器存储查询的对象，下次使用两个不同的时间戳发出请求时，只查询丢失的对象。这道题用小数来简化事情。

输入：

const intervals = [
  [3, 5],
  [7, 9],
];

const range = [2, 11];

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

间隔始终按开始日期排序，并且输入间隔从不重叠，因为合并和排序是事先完成的，根据此答案

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

输入：间隔：[[3, 5]]; 范围：[4, 8]; 输出：[[5, 8]]
输入：间隔：[[7, 11]]; 范围：[2, 8]; 输出：[[2, 7]]
输入：间隔：[[3, 5], [6, 8]]; 范围：[4, 7]; 输出：[[5, 6]]
输入：间隔：[[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

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

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

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

范围的开始在第一个元素之前。
范围的起点与第一个元素相交。
范围的末尾与最后一个元素相交。
范围的末尾超出了最后一个元素。
元素位于范围的起点和终点内。

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]));

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

Find all non-overlapping intervals within another interval

javascript

arrays

date

date-range

intervals