JS判断多个区间是否有交叉重叠

在开发Web应用程序时，我们经常遇到需要判断多个区间是否有交叉重叠的情况。例如，一个会议室预订系统需要检查新的预订时间是否与已有的预订时间重叠。在本篇博客中，我们将学习如何使用JavaScript来判断多个区间是否有交叉重叠。

理解问题

在开始编写代码之前，我们首先需要理解问题的要求。给定一组已知的区间，我们需要判断任意两个区间是否有交叉重叠。区间的表示通常使用两个整数来表示，分别代表起始点和终止点。

例如，我们有以下几个区间：

区间A: [1, 4]
区间B: [3, 6]
区间C: [7, 9]

在这个例子中，区间A和区间B有交叉重叠，因为3在区间A的范围内。然而，区间A和区间C没有交叉重叠。

解决方法

现在我们来讨论如何用JavaScript编写一个函数来判断区间是否有交叉重叠。

方法一：遍历比较

最简单的方法是遍历所有的区间，并进行两两比较。

我们可以用两个循环来遍历两个不同的区间，在每次迭代中，我们检查区间A的起始点和终止点是否在区间B的范围内。如果是，那么区间A和区间B有交叉重叠。

具体代码如下：

function checkOverlap(intervals) {
  for (let i = 0; i < intervals.length; i++) {
    for (let j = i + 1; j < intervals.length; j++) {
      const [startA, endA] = intervals[i];
      const [startB, endB] = intervals[j];
      if ((startA >= startB && startA <= endB) || (endA >= startB && endA <= endB)) {
        return true;
      }
    }
  }
  return false;
}

方法二：排序比较

上述方法的时间复杂度为O(n^2)，因为需要进行两两比较。我们可以通过排序来提高算法的效率，将区间按照起始点进行排序，然后进行一次遍历。

具体思路如下：

对区间进行排序，按照起始点从小到大的顺序。
从第二个区间开始，依次比较每个区间和前一个区间的终止点。
如果当前区间的起始点在前一个区间的范围内，则出现了交叉重叠。
如果没有出现交叉重叠，继续进行下一个区间的比较。

具体代码如下：

function checkOverlap(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);

  for (let i = 1; i < intervals.length; i++) {
    const [startA, endA] = intervals[i - 1];
    const [startB] = intervals[i];
    if (startB >= startA && startB <= endA) {
      return true;
    }
  }

  return false;
}

测试结果

让我们用一些测试用例来验证我们的代码是否正确：

const intervals1 = [[1, 4], [3, 6], [7, 9]];
console.log(checkOverlap(intervals1));  // true

const intervals2 = [[1, 3], [4, 6], [7, 9]];
console.log(checkOverlap(intervals2));  // false

const intervals3 = [[1, 2], [3, 4], [5, 6]];
console.log(checkOverlap(intervals3));  // false

以上代码执行后，应该得到正确的结果。

总结

本篇博客中，我们学习了如何用JavaScript判断多个区间是否有交叉重叠。我们讨论了两种不同的解决方法，并给出了相应的示例代码。希望这篇博客对你有所帮助！