时间范围减法：从一个时间集合中移除另一个时间段

本教程详细阐述了如何通过编程方式从一个时间范围集合中减去另一个时间范围集合所覆盖的部分。我们将探讨一种JavaScript实现方案，该方案能够识别并移除目标时间段内严格内嵌的冲突时间段，并对原始时间范围进行分割，最终生成一个不包含被移除部分的全新时间范围集合。

引言：时间范围的减法运算

在许多应用场景中，我们需要对时间范围进行复杂的管理和操作。其中一个常见需求是“时间范围的减法”，即从一个主时间范围集合中，移除另一个时间范围集合所覆盖的区域。例如，我们可能有一个可用时间段列表（xyz），以及一个预定或不可用时间段列表（abc），我们的目标是从可用时间段中剔除所有与不可用时间段重叠的部分。

考虑以下示例数据：

// 要移除的时间范围
abc: [
   {
      "start": "2021-11-25 16:30:00",
      "end": "2021-11-25 17:30:00"
   }
]

// 原始时间范围
xyz: [
   {
      "start": "2021-11-25 09:00:00",
      "end": "2021-11-25 18:00:00"
   },
   {
      "start": "2021-11-26 15:00:00",
      "end": "2021-11-26 19:00:00"
   }
]

我们的目标是修改 xyz 集合，使其不再包含 abc 中的时间段。根据上述示例，期望的结果是：

xyz: [
   {
      "start": "2021-11-25 09:00:00",
      "end": "2021-11-25 16:30:00"
   },
   {
      "start": "2021-11-25 17:30:00",
      "end": "2021-11-25 18:00:00"
   },
   {
      "start": "2021-11-26 15:00:00",
      "end": "2021-11-26 19:00:00"
   }
]

可以看到，xyz 中第一个范围 (09:00-18:00) 被 abc 中的 (16:30-17:30) 分割成了两部分。

核心算法解析

解决此类问题通常需要遍历两个时间范围集合，并对重叠部分进行判断和处理。基本思路是：

Nanonets

基于AI的自学习OCR文档处理，自动捕获文档数据

下载

1. 遍历主时间范围集合 (xyz)。
2. 对于 xyz 中的每一个时间范围，遍历要移除的时间范围集合 (abc)。
3. 检测冲突： 判断 abc 中的时间范围是否与当前的 xyz 时间范围发生重叠。
4. 处理冲突： 如果发生重叠，根据重叠类型（例如，完全包含、部分重叠）将 xyz 时间范围进行分割或调整。
5. 构建新集合： 将处理后的时间范围添加到新的结果集合中。

本教程将重点介绍一种JavaScript实现，它专注于处理 abc 中的时间范围严格内嵌于 xyz 中的情况。

JavaScript 实现

以下是实现上述逻辑的 JavaScript 代码示例：

var abc = [
   {
      "start": "2021-11-25 16:30:00",
      "end": "2021-11-25 17:30:00"
   }
];

var xyz = [
   {
      "start": "2021-11-25 09:00:00",
      "end": "2021-11-25 18:00:00"
   },
   {
      "start": "2021-11-26 15:00:00",
      "end": "2021-11-26 19:00:00"
   }
];

var newXyz = []; // 用于存储处理后的新时间范围集合

// 遍历 xyz 集合中的每个时间范围
for (var i in xyz) {
  // 将字符串日期转换为时间戳，便于比较
  var start = new Date(xyz[i]["start"]).getTime();
  var end = new Date(xyz[i]["end"]).getTime();
  var collisionDetected = false; // 标记当前 xyz 范围是否检测到冲突

  // 遍历 abc 集合中的每个时间范围，检查是否存在冲突
  for (var j in abc) {
    var start2 = new Date(abc[j]["start"]).getTime();
    var end2 = new Date(abc[j]["end"]).getTime();

    // 冲突检测条件：abc[j] 的开始时间在 xyz[i] 的内部
    // (即 abc[j].start > xyz[i].start 且 abc[j].start < xyz[i].end)
    if (start2 > start && start2 < end) {
      // 将 xyz[i] 的前半部分（从 xyz[i].start 到 abc[j].start）添加到新集合
      newXyz.push({"start": xyz[i]["start"], "end": abc[j]["start"]});

      // 进一步检查 abc[j] 的结束时间是否也在 xyz[i] 的内部
      // (即 abc[j].end < xyz[i].end)，这表明 abc[j] 完全包含在 xyz[i] 中
      if (end2 < end) {
        // 将 xyz[i] 的后半部分（从 abc[j].end 到 xyz[i].end）添加到新集合
        newXyz.push({"start": abc[j]["end"], "end": xyz[i]["end"]});
      }

      collisionDetected = true; // 标记已检测到冲突
      break; // 针对当前 xyz[i] 范围，只处理第一个发现的 abc[j] 冲突，然后跳出内层循环
    }
  }

  // 如果当前 xyz[i] 范围没有检测到任何冲突，则将其原样添加到新集合
  if (collisionDetected == false) {
    newXyz.push({"start": xyz[i]["start"], "end": xyz[i]["end"]});
  }
}

xyz = newXyz; // 将处理后的新集合赋值回 xyz
console.dir(xyz); // 打印结果

代码解析

1. 数据初始化： abc 和 xyz 分别存储了要移除的时间范围和原始时间范围。newXyz 是一个空数组，用于收集处理后的时间范围。
2. 外层循环 (for i in xyz)： 遍历 xyz 中的每一个时间段。
3. 时间戳转换： new Date().getTime() 将日期字符串转换为 Unix 时间戳，这使得时间点之间的比较更加直接和准确。
4. 内层循环 (for j in abc)： 对于 xyz 中的当前时间段 xyz[i]，遍历 abc 中的所有时间段 abc[j]，以查找重叠。
5. 冲突检测 (start2 > start && start2 < end)： 这个条件判断 abc[j] 的开始时间是否严格位于 xyz[i] 的开始时间和结束时间之间。这意味着 abc[j] 的起始点落在了 xyz[i] 内部。
6. 分割 xyz[i] 的前半部分： 如果检测到冲突，newXyz.push({"start": xyz[i]["start"], "end": abc[j]["start"]}) 会将 xyz[i] 从其起始点到 abc[j] 起始点之间的部分添加到结果中。
7. 分割 xyz[i] 的后半部分 (if (end2 < end))： 进一步检查 abc[j] 的结束时间是否也严格位于 xyz[i] 的结束时间之前。如果这个条件也满足，则说明 abc[j] 完全被 xyz[i] 包裹。此时，newXyz.push({"start": abc[j]["end"], "end": xyz[i]["end"]}) 会将 xyz[i] 从 abc[j] 结束点到 xyz[i] 结束点之间的部分添加到结果中。
8. collisionDetected 和 break： 一旦为 xyz[i] 找到了一个 abc[j] 冲突并进行了处理，collisionDetected 标志被设为 true，并通过 break 跳出内层循环。这意味着当前的实现只会处理 xyz[i] 与 abc 集合中第一个发现的冲突。
9. 无冲突处理： 如果 xyz[i] 在与 abc 集合的所有时间段比较后都没有检测到冲突 (collisionDetected 仍为 false)，则将 xyz[i] 完整地添加到 newXyz 中。
10. 更新 xyz： 最后，xyz = newXyz 将处理后的结果赋值回 xyz 变量。

注意事项与局限性

当前的实现简洁有效，但在实际应用中存在一些重要的局限性，需要开发者根据具体需求进行评估和扩展：

• 严格内嵌假设：
  • 此代码仅处理 abc 范围严格包含在 xyz 范围内部的情况（即 abc.start > xyz.start 且 abc.end < xyz.end）。
  • 它不处理 abc 范围与 xyz 范围边界重叠（abc.start == xyz.start 或 abc.end == xyz.end）的情况。
  • 它也不处理 abc 范围部分重叠（例如 abc 开始于 xyz 之前但结束于 xyz 内部，或反之）的情况。
• 单次冲突处理：
  • 对于 xyz 集合中的每一个时间范围，代码只处理与 abc 集合中第一个检测到的冲突，然后就跳出内层循环。这意味着如果一个 xyz 范围与 abc 集合中的多个范围重叠，只有第一个重叠会被处理。
  • 要处理一个 xyz 范围与多个 abc 范围的冲突，需要更复杂的逻辑，例如，在内层循环结束后，对 newXyz 中新生成的片段再次进行冲突检测，或者采用更高级的区间合并/分割算法。
• 输入范围的假设：
  • 代码假定 abc 和 xyz 集合内部的时间范围都没有重叠。如果存在内部重叠，可能需要预先对这些集合进行合并或排序处理。
  • 没有对输入时间范围进行排序，但在处理复杂重叠时，对时间范围按起始时间排序通常是提高效率和正确性的第一步。
• 效率：
  • 嵌套循环的复杂度为 O(m*n)，其中 m 是 xyz 的长度，n 是 abc 的长度。对于非常大的数据集，这种方法可能效率不高。更优化的解决方案可能涉及对时间范围进行排序，然后使用线性扫描或区间树等数据结构。

总结

本教程提供了一种在 JavaScript 中从一个时间范围中移除另一个严格内嵌时间范围的实用方法。通过将日期字符串转换为时间戳进行比较，并根据冲突情况对时间范围进行分割，我们可以有效地实现这一需求。然而，理解其局限性至关重要，特别是在处理更复杂的重叠模式或大规模数据集时，可能需要采用更健壮的算法和库来满足生产环境的需求。