C++ 合并重叠区间

合并重叠区间 是一个常见的计算问题，出现在各种领域，包括计算机科学、数学以及诸如调度、日历管理和数据分析等实际应用中。目标是接收一组区间，每个区间代表一个值范围，并将任何重叠的区间合并为一个单一的、集成的区间。此过程简化了数据表示，并有助于各种任务，例如查找可用时间段、优化计划或减少数据复杂性。

区间表示：区间通常表示为一对值[start, end]，其中start是区间的开始，end是结束点。它表示一个闭区间，意味着开始点和结束点都包含在区间内。

排序：为了有效地合并重叠区间，按起始值对区间进行排序至关重要。排序确保在确定重叠时首先考虑最早开始时间的区间。通常使用快速排序或归并排序等排序算法。

合并过程

• 初始化一个空的結果集以存储合并后的区间。
• 逐一迭代已排序的区间，从第一个区间开始。
• 对于每个区间，检查它是否与先前合并的区间（如果有）重叠，方法是将其开始值与最后一个合并的区间的结束值进行比较。
• 假设存在重叠（即start <= last_merged_end），则将当前区间与最后一个合并的区间合并。为此，将最后一个合并的区间的结束值更新为其当前结束值与当前区间的结束值中的最大值。
• 如果没有重叠，则将当前区间添加为新的合并区间添加到结果集中。

结果：处理完所有区间后，结果集将包含一组不重叠的区间，这些区间覆盖的范围与原始区间相同，但重叠区间已合并为一个。

此过程简化了区间表示，使其更易于处理和分析数据。需要注意的是，此操作的效率取决于排序步骤，对于 n 个区间，其时间复杂度通常为O(n log n)。排序完成后，合并步骤是线性的，因此合并算法的总体时间复杂度由于排序步骤而为O(n log n)。

程序 1：暴力枚举法（二次方时间）

此方法涉及将每个区间与所有其他区间进行比较以检查重叠。对于每个区间，迭代所有其他区间并合并重叠的区间。其时间复杂度为O(n^2)，但实现起来很简单。

输出

[1, 6] [8, 10] [15, 18]

解释

函数定义

• 代码定义了一个名为mergeOverlappingIntervals的函数。
• 它以整数对的向量作为输入，表示区间。
• 该函数返回一个合并区间向量。

算法概述

• 该函数使用暴力枚举法来合并重叠的区间。
• 它迭代输入向量中的每个区间，并检查与其他所有区间的重叠情况。
• 如果找到重叠，则合并区间。
• 合并后的区间存储在一个新向量中并返回。

初始化

• 创建了一个名为 mergedIntervals 的向量来存储合并后的区间。

主循环

• 代码逐一迭代输入向量中的每个区间。
• 它使用嵌套循环将当前区间与所有其他区间进行比较。

重叠检测

• 它使用开始和结束值检查当前区间与其他区间之间是否存在重叠。

合并重叠区间

• 如果检测到重叠，则代码会更新当前区间以表示合并后的区间。
• 合并后的区间的开始设置为两个区间开始的最小值，结束设置为两个区间结束的最大值。

将合并后的区间添加到结果中

• 在将当前区间与所有其他区间进行比较后，将其添加到mergedIntervals向量中。
• 代码确保合并后的区间不会在结果中重复。

返回结果

• 该函数返回包含合并后的区间的mergedIntervals向量。

复杂度分析

时间复杂度

• 主循环迭代输入向量中的每个区间，产生O(n)次迭代，其中 n 是区间的数量。
• 主循环中的每个区间都有一个嵌套循环，该循环迭代所有其他区间。在最坏的情况下，此嵌套循环会将当前区间与每个其他区间进行比较，从而为每个主循环中的区间产生O(n)次比较。
• 因此，总体时间复杂度为O(n^2)，其中 n 是区间的数量。

空间复杂度

• 空间复杂度主要由 mergedIntervals 向量中合并区间的存储决定。
• 在最坏的情况下，如果无法合并任何区间，则mergedIntervals向量将包含与输入向量相同数量的区间，从而产生O(n)的空间复杂度。
• 此外，还有一些用于比较和临时存储的辅助变量，但它们的空间使用相对较小，不会显著影响总体空间复杂度。

总之，提供的暴力枚举法具有O(n^2)的时间复杂度，O(n)的空间复杂度，其中 n 是输入向量中区间的数量。与基于排序的方法相比，此方法效率较低，基于排序的方法可以使用O(n)的空间复杂度实现O(n log n)的时间复杂度。

程序 2：排序和合并（线性算术时间）

步骤 1：排序区间

• 在此方法中，第一步是根据起始值对输入区间进行排序。
• 排序至关重要，因为它有助于将重叠的区间分组在一起，从而更容易识别和合并它们。
• 此处通常使用快速排序或归并排序等通用排序算法，其平均时间复杂度为O(n log n)。

步骤 2：合并重叠区间

• 对区间进行排序后，您将按排序顺序迭代它们。
• 您维护一个变量，通常称为mergedIntervals或类似的名称，以存储合并后的区间。

迭代合并过程

• 从第一个区间（起始值最小的那个）开始，将其视为“当前区间”。
• 移动到下一个区间，并检查它是否与当前区间重叠。
• 之后，将当前区间的开始与下一个区间的结束进行比较，以确定重叠。
• 如果当前区间的开始小于或等于下一个区间的结束，则意味着它们重叠。
• 如果它们重叠，则通过将当前区间的结束更新为其当前结束值和下一个区间结束值中的最大值来合并这两个区间。
• 如果不存在重叠，则将当前区间添加到结果（mergedIntervals）中，因为您已经找到了此合并区间的结束。
• 继续此过程，逐一遍历排序后的区间，在遇到重叠时进行合并。

示例

输出

[1, 6] [8, 10] [15, 18]

解释

• 在此示例中，定义了一个名为mergeOverlappingIntervals的函数，该函数以区间向量作为输入。
• 代码检查区间输入向量是否为空。如果为空，则函数返回一个空向量，因为没有要合并的区间。
• 使用std::sort根据起始值对区间进行排序。排序可确保重叠的区间相邻，从而简化合并过程。
• 创建了一个名为mergedIntervals的新向量来存储合并后的区间。
• 第一个区间（起始值最小的那个）被添加为初始合并区间到 mergedIntervals 中。
• 之后，代码从第二个区间开始迭代已排序的区间。
• 它检查与最后一个合并区间（mergedIntervals 向量末尾的那个）是否存在重叠。
• 如果存在重叠，则代码通过在必要时扩展最后一个合并区间的结束来合并当前区间与最后一个合并区间。
• 如果不存在重叠，则当前区间作为新的合并区间添加到 mergedIntervals 向量中。
• mergedIntervals向量现在包含没有重叠的合并区间。这些合并后的区间表示从输入区间获得的非重叠范围。
• 该函数将 mergedIntervals 向量作为结果返回。

复杂度分析

时间复杂度

• 此方法的时间复杂度主要由排序步骤决定，其时间复杂度为O(n log n)，其中 n 是区间的数量。
• 接下来的合并步骤在时间复杂度上是线性的，因为它处理每个区间一次。
• 总体而言，由于排序步骤，此方法的时间复杂度为O(n log n)，并且被认为可以高效处理大型数据集。

空间复杂度

• 空间复杂度主要取决于存储已排序区间和合并区间所需的空间。
• 排序通常在原始区间上原地进行，因此不会显著影响空间复杂度。
• 合并后的区间存储在单独的向量或数据结构中，其空间复杂度为O(n)，因为如果没有重叠，它可能包含所有区间。

总之，“排序和合并”方法通过排序步骤有效地合并重叠区间，时间复杂度为O(n log n)。它适用于处理大型数据集，并且是实践中解决此问题的标准方法。

程序 3：基于栈的方法（线性时间）

• 根据开始值对区间进行排序。
• 初始化一个空栈来存储合并后的区间。
• 迭代已排序的区间，如果它们不与栈顶区间重叠，则将区间推入栈中，如果重叠，则合并它们。

示例

输出

[1, 6] [8, 10] [15, 18]

解释

• 定义了一个名为mergeOverlappingIntervals的函数，该函数以区间向量作为输入。
• 代码检查区间输入向量是否为空。如果为空，则函数返回一个空向量，表示没有要合并的区间。
• 使用std::sort根据起始值对区间进行排序。排序可确保重叠的区间相邻，从而更容易合并它们。
• 创建了一个名为intervalStack的栈，用于在合并过程中保存区间。
• 代码从第二个区间开始迭代已排序的区间。
• 它检查与栈顶区间（最后一个合并区间）是否存在重叠。
• 如果存在重叠，则代码通过在必要时扩展最后一个合并区间的结束来合并当前区间与栈顶区间。
• 如果不存在重叠，则当前区间作为新的要合并的区间推入栈中。
• 处理完所有区间后，从栈中提取合并后的区间，并存储在一个名为 mergedIntervals 的向量中。
• 代码将mergedIntervals向量中的区间顺序反转，以获得正确顺序（从左到右）的合并区间。
• 该函数返回 mergedIntervals 向量，该向量现在包含合并后的非重叠区间。

总之，此基于栈的方法通过迭代排序后的区间并使用栈来管理合并过程，从而有效地合并重叠的区间。结果是包含合并区间的向量，没有重叠。

复杂度分析

时间复杂度

• 初始对区间进行排序需要O(n log n)的时间，其中“n”是区间的数量。
• 随后的迭代已排序区间是线性的，即O(n)。
• 每个区间被推入或从栈中弹出一次，这也需要O(n)。
• 总体而言，时间复杂度由排序步骤决定，时间复杂度为O(n log n)。

空间复杂度

空间复杂度主要取决于附加数据结构的使用

• 创建了排序后的区间副本，这需要O(n)的附加空间。
• 在合并过程中使用栈来保存区间，在最坏的情况下，该栈可能会暂时存储多达O(n)个区间。
• mergedIntervals向量存储合并后的区间，其最大大小也可能为O(n)。
• 因此，由于附加数据结构，空间复杂度为 O(n)。
• 用于合并重叠区间的基于栈的方法具有O(n log n)的时间复杂度，O(n)的空间复杂度，使其成为处理大型区间数据集的有效方法。

程序 4：二叉搜索树方法

在 C++ 中合并重叠区间的一种替代方法是使用二叉搜索树 (BST) 数据结构。这是该方法的高级说明

定义区间节点结构：创建一种结构来表示区间节点，其中包含区间的开始和结束值以及 BST 中左子节点和右子节点的引用。

将区间插入 BST：根据其开始值将每个区间插入 BST。插入时，需要处理新区间可能与现有节点重叠的情况。在这种情况下，将重叠区间节点的结束值更新为新区间结束值和现有节点结束值中的最大值。

遍历 BST：对 BST 进行中序遍历将按排序顺序获得区间。在遍历树时，您可以累积合并后的区间，并在遇到重叠时根据需要进行更新。

收集合并后的区间：在中序遍历期间，您可以维护一个栈来跟踪合并后的区间。在访问每个区间节点时，将其与栈顶进行比较以识别重叠。如果存在重叠，则合并区间；否则，将当前区间推入栈中。

示例

输出

[1, 6] [8, 10] [15, 18]

解释

在此示例中，代码首先包含必要的 C++ 库，用于输入/输出（iostream）、处理向量（vector）以及使用栈（stack）。

它定义了两个自定义数据结构

Interval：表示具有开始和结束值的区间。

IntervalNode：表示二叉搜索树（BST）中的节点，该节点包含一个区间以及左右子节点。

• insertInterval函数负责将区间插入 BST，同时确保重叠区间被合并。如果新区间与树中的现有区间重叠，它会更新现有区间的边界以包含这两个区间。
• inOrderTraversal函数执行 BST 的中序遍历，这对于收集合并后的区间至关重要。它按排序顺序将区间附加到mergedIntervals向量。

主函数mergeOverlappingIntervals协调整个过程

• 它初始化一个空的 BST（根）。
• 迭代输入区间，将它们插入 BST。
• 调用 inOrderTraversal 函数将合并后的区间填充到mergedIntervals向量。
• 合并后的区间作为向量从mergeOverlappingIntervals返回。
• 在主函数中，提供了示例区间，代码将合并后的区间打印到控制台。
• 程序最后返回 0，表示成功执行。
• 此方法使用二叉搜索树来有效地合并重叠区间，从而得到一个非重叠区间向量。核心思想是使用 BST 按排序顺序维护区间，这简化了合并过程并产生了所需的合并区间。

复杂度分析

时间复杂度

• 将“n”个区间插入 BST 的时间复杂度可能有所不同，但对于平衡良好的树，通常为O(n * log n)。在最坏的情况下，当树退化（线性）时，可能为O(n^2)。然而，平均而言，对于平衡良好的树，它倾向于O(n * log n)。
• BST 的中序遍历需要O(n)时间，因为它处理每个节点一次。
• 总体而言，代码的时间复杂度主要由 BST 插入步骤决定，对于平衡树，平均为O(n * log n)。

空间复杂度

• 用于在 BST 中存储区间的时间复杂度为O(n)，因为在最坏的情况下，BST 可能包含“n”个节点（每个区间一个）。
• mergedIntervals向量存储合并后的区间，其最大大小也可能为“n”。
• 代码使用少量附加空间用于变量和函数调用栈，但这些不会显著影响总体空间复杂度。
• 由于 BST 和 mergedIntervals 向量中的区间存储，代码的总体空间复杂度为O(n)。

合并重叠区间的好处

合并重叠区间有几个好处。合并重叠区间的一些主要好处如下

数据减少：合并重叠区间可减少要管理的数据量。在具有大量区间数据集的场景中（例如调度）非常有用，其中合并后的区间代表集成的时段，节省了内存和计算资源。

改进可视化：合并后的区间简化了数据可视化。您无需处理大量单个区间，而是可以使用较少数量的合并区间来表示数据，从而使其在图形或图表中更易于解释和显示。

简化的分析：合并后的区间简化了数据分析任务。当区间合并时，您可以专注于更广泛的时间段，而不是分析单个事件或区间。这种简化可以导致更有效和更直接的分析。

合并重叠区间的缺点

合并重叠区间有几个缺点。合并重叠区间的一些主要缺点如下

精度损失：合并区间可能导致精度损失。当区间合并时，您会丢失有关事件的具体时间或发生在合并区间内的事件的信息。在需要精确时间的应用中，这可能是一个限制。

复杂性：实现区间合并算法可能很复杂，尤其是在处理大量区间或需要考虑其他约束时。排序和合并过程可能会引入计算开销。

特定于应用：区间合并的优点和局限性通常是特定于应用的。在一个上下文中有效的方法在另一个上下文中可能不那么有效。理解问题的具体要求对于选择正确的方法至关重要。