算法:合并重叠段

Question

我有以下ADT(未排序): List<Segment>

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

他们代表这种情况:

如何进行合并阶段(示例中为绿色箭头)？显然,我需要迭代列表,每个段与所有其他段进行比较,并且如果可能的话,为每个段进行简单的合并(这很容易).但是在第二次迭代中,我需要以某种方式返回到列表的开头并重新开始...所以我很难找到这个算法如何收敛.

编辑:段可以是圆形 - 从1.75pi到0.5pi等...

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);

    }
}

Answer 2

按起点对细分进行排序.

然后,对于每个段,如果其起点位于前一段的起点和终点之间且其终点大于前一段的终点,则将前一段的终点设置为该段的终点并删除/忽略当前部分.

如果当前段完全包含在前一段中,则只需删除/忽略它.

这是O(n log n)因为排序,您不需要将每个段与所有其他段进行比较.

小心你如何删除或忽略.它应该是一个O(1)操作.例如,保留一个始终存储前一个未删除段的变量,也可以保留一些已删除段的标志,以便您知道最后要收集哪些段..remove()对集合的操作可以是O(n),并且您希望避免这种情况.

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 to >0或>0 to 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]

在上边界关系的情况下,更好地处理+和-在次序,使得你避免发射两个相等的边界.