合并重叠间隔行为

Question

我正在尝试解决合并重叠间隔问题，并在下面提供了有效的解决方案。但是，有一段逻辑我无法理解。即 currentInterval[1] 更新为 currentInterval[1] 和 nextInterval[1] 之间的最大值的部分。这段代码还更新了 mergedIntervals 数组中的最后一个数组，我不完全理解这是如何发生的，因为我没有看到 currentInterval 如何与 mergedIntervals 中的最后一个数组链接。有人可以解释当我们设置 currentInterval[1] 时 mergedIntervals 是如何更新的吗？

 const array = [
      [1, 2],
      [4, 7],
      [9, 10],
      [3, 5],
      [6, 8],
    ];

    function mergeOverlappingIntervals(array) {
      let sortedIntervals = array.sort(function (a, b) {
        return a[0] - b[0];
      });
    
      let mergedIntervals = [];
      let currentInterval = sortedIntervals[0];
      mergedIntervals.push(currentInterval);
    
      for (let nextInterval of sortedIntervals) {
        if (currentInterval[1] >= nextInterval[0]) {
          currentInterval[1] = Math.max(
            currentInterval[1],
            nextInterval[1],
          );
        } else {
          currentInterval = nextInterval;
          mergedIntervals.push(nextInterval);
        }
      }
    
      return mergedIntervals;
    }

const result = mergeOverlappingIntervals(array);
console.log('result', result);

Answer 1

我想您可能需要了解此算法的见解之一如下：

即使区间已经被压入结果数组，它仍然可以被修改。

这就是发生的事情。 currentInterval 始终是已经压入结果数组的间隔。这在循环开始之前就已经发生了。

但后来，这个区间 currentInterval 可能会突变（当 if 条件为真时）。更准确地说，它可能会扩展。这样的扩展在结果数组中是有效的，即使 mergedIntervals 在 if 块中没有被提及，它间接地确实发生了变异，因为 currentInterval 是它的成员。

让我们用这个算法的简单运行来说明这一点。

输入：[[1, 5], [3, 7]]

就在循环开始之前，我们遇到了这种情况：

mergedIntervals
┌─────────┬───────────────────────┐
│ index:  │         0             │
├─────────┼───────────────────────┤
│ content:│ currentInterval       │
│         │ ┌─────────┬───┬───┐   │
│         │ │ index:  │ 0 │ 1 │   │
│         │ ├─────────┼───┼───┤   │
│         │ │ content:│ 1 │ 5 │   │
│         │ └─────────┴───┴───┘   │
└─────────┴───────────────────────┘

此可视化显示具有一个槽（索引 0）的外部数组，其内容是具有两个槽（索引 0 和 1）的内部数组。这里的关键是变量 currentInterval 引用了位于 mergedIntervals.

中的数组

现在，当循环进行第一次迭代时，它确实是一个无用的迭代，因为它让 nextInterval 成为输入区间中的第一个区间，这是 与 currentInterval 相同的 间隔。 if 条件为真，但是 Math.max 表达式将与 currentInterval[1] 已经具有的值相同：5。所以这是一个无用的迭代，但它也没有造成任何伤害.

第二次迭代很有趣。这里 nextInterval 是输入中的第二个区间：[3, 7]。 if 条件为真（因为 5 >= 3），因此 currentInterval[1] 得到 nextInterval[1] 的值，即 7。这有效地扩展了当前区间，我们得到：

mergedIntervals
┌─────────┬───────────────────────┐
│ index:  │         0             │
├─────────┼───────────────────────┤
│ content:│ currentInterval       │
│         │ ┌─────────┬───┬───┐   │
│         │ │ index:  │ 0 │ 1 │   │
│         │ ├─────────┼───┼───┤   │
│         │ │ content:│ 1 │ 7 │   │
│         │ └─────────┴───┴───┘   │
└─────────┴───────────────────────┘

注意这如何影响结果数组！

如果第二个区间更小以至于它完全落在 currentInterval 内（例如 [3, 4]），则什么都不会改变，因为 Math.max 表达式会 select currentInterval[1]。这确实是正确的做法。

在这个简单的示例中，循环结束，输出确实是我们期望得到的。

我希望这能阐明算法。

合并重叠间隔行为

Merge overlapping intervals behavior

javascript

arrays

algorithm

array-algorithms