javascript - 间隔范围插入间隔而不合并现有间隔

Question

问题描述: 这个想法是在现有间隔中插入新间隔，该新间隔不会与现有间隔合并，而是填充间隔之间缺失的间隙。 (这不是区间合并问题)

例如，将区间 [0, 7] 插入到区间 [[0, 1], [3, 5]] 将产生新的区间，其中的间隙被填充 [[0, 1], [1, 3], [3 , 5], [5, 7]]。

间隔范围已按从小到大排序[[0, 1], [3, 5]]。

我当前的解决方案有点“ splinter ”，我最终使用了太多的 if 检查来覆盖一些特殊情况，这使得一切都比需要的更加复杂。我正在寻找更好的方法来简化条件部分。代码底部包含测试用例，以及我的解决方案失败的情况。

我的算法失败并产生错误结果的测试用例:

assert.deepEqual( // Broken
    insertIntervalSec([[1, 5], [7, 10]], [4, 12]),
    [[1, 5], [5, 7], [7, 10], [10, 12]],
);
assert.deepEqual(insertIntervalSec([[1, 1]], [1, 3]), [[1, 3]]); // Broken

function isOverLapping(a, b) {
    return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
}

function insertIntervalSec(arr, interval) {
    const result = [];
    let i = 0;

    const contains = (a, b) => {
        return a[0] >= b[0] && a[1] <= b[1]
    };

    if (arr.length <= 0) {
        result.push(interval);
        return result;
    }
    if (arr.length === 1 && contains(interval, arr[0])) {
        result.push(interval);
        return result;
    }

    // Start point
    if (interval[1] >= arr[0][0] && isOverLapping(interval, arr[0])) {
        result.push([interval[0], arr[0][0]]);
    } else if (interval[1] <= arr[0][0]) {
        result.push([interval[0], Math.min(interval[1], arr[0][0])]);
    }

    while (i < arr.length) {
        const current = arr[i];
        result.push(arr[i]);

        if (!contains(interval, arr[i]) && isOverLapping(arr[i], interval)) {
            const next = arr[i + 1];

            // Special handling for the last item
            if (next !== undefined) {
                if (interval[1] > current[1]) {
                    result.push([current[1], next[0]]);
                }
            } else {
                if (interval[0] <= current[0] && interval[1] <= current[1]) {
                    // TODO: No action
                } else if (interval[0] >= current[0] || interval[1] >= current[0]) {
                    result.push([current[1], interval[1]]);
                }
            }
        }
        i++;
    }

    // End point
    const len = arr.length;
    const last = arr[len - 1];
    if (last[1] <= interval[0] && !isOverLapping(last, interval)) {
        result.push(interval);
    }

    return result;
}

assert.deepEqual(
    insertIntervalSec([[1, 5], [10, 15], [20, 25]], [12, 27]),
    [[1, 5], [10, 15], [15, 20], [20, 25], [25, 27]]
);

assert.deepEqual(
    insertIntervalSec([[1, 5], [10, 15], [20, 25]], [-3, 0]),
    [[-3, 0], [1, 5], [10, 15], [20, 25]]
);

assert.deepEqual(
    insertIntervalSec([[1, 5], [10, 15], [20, 25]], [-3, 3]),
    [[-3, 1], [1, 5], [10, 15], [20, 25]]
);

assert.deepEqual(
    insertIntervalSec([[0, 5], [10, 15], [20, 25]], [15, 15]),
    [[0, 5], [10, 15], [20, 25]]
);
assert.deepEqual(
    insertIntervalSec([[0, 5], [10, 15], [20, 25]], [20, 21]),
    [[0, 5], [10, 15], [20, 25]]
);
assert.deepEqual(
    insertIntervalSec([[0, 5], [10, 15], [20, 25]], [26, 27]),
    [[0, 5], [10, 15], [20, 25], [26, 27]]
);
assert.deepEqual(
    insertIntervalSec([[0, 5], [10, 15], [20, 25]], [25, 27]),
    [[0, 5], [10, 15], [20, 25], [25, 27]]
);
assert.deepEqual(insertIntervalSec([], [25, 27]), [[25, 27]]);
assert.deepEqual(insertIntervalSec([[1, 1]], [1, 1]), [[1, 1]]);
assert.deepEqual( // Broken
    insertIntervalSec([[1, 5], [7, 10]], [4, 12]),
    [[1, 5], [5, 7], [7, 10], [10, 12]],
);
assert.deepEqual(insertIntervalSec([[1, 1]], [1, 3]), [[1, 3]]); // Broken

assert.deepEqual(
    insertIntervalSec2([[5, 5]], [6, 6]),
    [[5, 5], [6, 6]]
);

assert.deepEqual(
    insertIntervalSec2([[1, 3]], [6, 6]),
    [[1, 3], [6, 6]]
);

Answer 1

除了最后一个测试用例(请参阅问题评论)之外，这通过了所有测试。基本思想是您只需跟踪 start 变量，该变量指示您使用了多少插入范围。这使您可以将范围缩小到三种情况:

1. 插入的间隔完全适合当前项目
2. 迭代中的当前项完全适合插入的间隔之前
3. 迭代中的项目重叠。

迭代完项目后，您可以检查插入的范围是否还有要插入的内容:

function insertIntervalSec(arr, insert) {
  let start = insert[0]
  let res = []
  for (i = 0; i < arr.length; i++) {
    let a = arr[i]
    // smaller item in range
    if (a[0] <= start) {
      res.push(a)
      start = Math.max(a[1], start)
      continue
    }
    // moved past inserted interval add rest of arr
    if (start >= insert[1]) {
      res.push(...arr.splice(i))
      break
    }

    // fill in spaces
    let end = Math.min(insert[1], a[0])
    res.push([start, end], a)
    start = a[1]
  }
  // clean up left over range
  if (start < insert[1]) res.push([start, insert[1]])

  return res
}

console.log(insertIntervalSec([ [1, 5],[10, 15],[20, 25]], [-2, 27]))