算法：合并重叠的线段

Question

我有一个ADT（未排序）如下：List<Segment>。

//direction is from 0 to 2pi
class Segment {
    int start;
    int end;
}

他们举的例子如下情况： 如何进行合并阶段（上图中绿色箭头）？显然，我需要遍历整个列表，并比较每个片段与其他所有片段，对于每一对可简单合并的片段（这很容易实现），但在第二次迭代中，我需要回到列表开头重新开始等等......所以我很难找到这个算法将如何收敛。

编辑：段可以是环形的-从1.75pi到0.5pi等......

- michael

---

你的列表是有序还是随机的？ - Tim

它是循环的吗？也就是说，你可以从1.5pi开始一个段，然后经过2pi到0.5pi吗？ - Petr

@Petr 我之前没有注意到，但实际上是可以循环的... - michael

Answer 1

按照开始时间对段进行排序。

创建一个堆栈来存储合并的区间。

将排序后数组的第一个元素添加到堆栈中，然后对于数组中的每个元素，将其与堆栈顶部的元素进行比较。

如果开始时间大于堆栈顶部元素的结束时间，则将区间添加到堆栈中。

如果开始时间小于堆栈顶部元素的结束时间，则更新堆栈顶部元素的结束时间以匹配新元素的结束时间。

处理整个数组后，结果堆栈应包含合并的区间。

Java实现：

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        Deque<Interval> stack = new ArrayDeque<Interval>();

        Collections.sort(intervals, new Comparator<Interval>() {
                public int compare(Interval p1, Interval p2) {
                    return Integer.compare(p1.start, p2.start);
                }
            }
        );

        if (intervals.size() < 1) {
            return intervals;
        }
        stack.push(intervals.get(0));

        for (int j = 1; j < intervals.size(); j++) {
            Interval i = intervals.get(j);
            Interval top  = stack.peek();
            if (top.end < i. start) {
                stack.push(i);
            }
            else if (top.end < i.end) {
                top.end = i.end;
            }
        }
        return new ArrayList<Interval>(stack);

    }
}

- alampada

Answer 2

按起始点对片段进行排序。

然后，对于每个片段，如果它的起始点在前一个片段的起始点和结束点之间，并且它的结束点大于前一个片段的结束点，则将前一个片段的结束点设置为该片段的结束点，并删除/忽略当前片段。

如果当前片段完全包含在前一个片段中，则只需删除/忽略它。

由于排序，这是 O(n log n) 的算法，你不需要将每个片段与所有其他片段进行比较。

要注意如何进行删除或忽略。这应该是一个 O(1) 的操作。例如，保持一个变量，始终存储前一个未被删除的片段，并可能使用一些标记来标记已删除的片段，以便在最后可以收集到哪些片段被删除了。.remove() 操作可能是 O(n) 的，你需要避免这种情况。

- IVlad

---

@IVIad 感谢您对复杂性分析的关注。 - michael

Answer 3

将所有端点放入一个数组中，并为它们分配极性（+然后是-）。然后对列表进行排序。

当您按递增值遍历列表时，只需更新重叠段的计数器即可。

0+ 0.75- 0.5+ 1- 1.25+ 2-

接着，排序完成，

0+ 0.5+ 0.75- 1- 1.25+ 2-

给出计数（初始化为0）

1 2 1 0 1 0

因此，过渡区间的边界应为（从0到>0或>0到0）。

0 1 1.25 2

---

这也可以在原地、无需额外标志的情况下完成。

您可以将start和end值分别就地排序（不要整体移动Segments），这样极性就保持不变了。

然后遍历列表，将其视为两个已排序列表的合并（使用两个独立索引），并维护重叠计数器。您可以原地覆盖边界，因为合并的结果没有更多间隔。

从以下内容开始：

[0 0.75][0.5 1][1.25 2]

这两个列表已经意外地被排序了。

0 0.5 1.25 (+)
0.75 1 2   (-)

继续合并，将按顺序选择元素。

+ + - - + -

并且最终结果是通过移动数值得到的。

[0 1][1.25 2][x x]

---

如果边界存在并列的情况，最好按照一定顺序处理+和-，以避免发出两个相等的边界。

- user1196549

Answer 4

我将为其他答案添加处理循环性的方法，即如果您有一些分段循环超过2pi该怎么办。

有两种处理方式。一种是将每个这样的段简单分成两个部分：一个从任何位置到2pi，另一个从零到任何位置。完成此操作后，将问题解决为非循环问题，然后如果您有一个从零开始的段和一个以2pi结束的段，则只需合并它们即可。

第二种方法专门针对Yves Daoust的答案。你所需要做的就是知道有多少段覆盖了零点（您可以轻松计算出这个值）。完成此操作后，您不需要用零来初始化“计数”，而是用这个覆盖段数的数字来初始化。

- Petr