代码之家 › 专栏 › 技术社区 › Risto Novik

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

algorithm javascript

Risto Novik · 技术社区 · 7 年前

问题描述: 其思想是在现有间隔中插入新间隔,新间隔不与现有间隔合并,而是填充间隔之间缺失的间隔。( 这不是间隔合并问题 )

例如,将间隔[0,7]插入到间隔[0,1],[3,5]]将生成新间隔,其中填充了间隔[0,1],[1,3],[3,5],[5,7]]。

间隔范围已排序 最小到较大 [[0, 1], [3, 5]] .

我目前的解决方案有点“支离破碎”,最后我用了太多的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]]
);

1 回复 | 直到 7 年前

Mark 7 年前

除了最后一个测试用例(参见对问题的评论),这将通过所有测试。基本的想法是你只需跟踪 start 变量,指示已使用的插入范围的位置。这样可以将范围缩小到三种情况:

插入的间隔完全在当前项之前
迭代中的当前项完全适合插入的间隔之前
迭代中的项重叠。

在迭代这些项之后,可以检查插入的范围是否还有任何要插入的内容:

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