算法：合并重叠段 [英] Algorithm: Merge overlapping segments

问题描述

我有以下ADT（未排序）：列表＆lt;段＆GT;

I have following ADT (not sorted): List<Segment>

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

他们再比如presenting这种情况：

如何使合并阶段（绿色箭头的例子）？很显然，我需要遍历列表，每个段比较其他各阶层，并为每对夫妇如果可能的话进行简单的合并（这是很容易）。但随后在第二次迭代，我需要以某种方式返回到列表的开头并开始了等...所以我很难找到这个算法如何收敛。

How to make the merging phase (green arrow in the example)? Obviously I need to iterate over the list and each segment compare to all other segments, and for each couple if possible to make simple merge (this is easy). But then in the second iteration I need somehow to return to the beginning of the list and start over etc... So I struggle to find how this algorithm will converge.

编辑：段可以circular-从1.75pi到0.5pi等等...

The segments can be circular- From 1.75pi to 0.5pi etc...

推荐答案

通过启动时间排序的段。

Sort the segments by starting time.

创建堆栈将存储合并区间。

Create a stack which will store the merged intervals.

排序后的数组的第一个元素添加到栈中，然后对阵列中的每个元素，在堆栈的顶部比较它的元素

Add the first element of the sorted array to the stack, then for each element in the array, compare it to the element at the top of the stack

如果开始时间比在堆栈的顶部元件的结束时间时，时间间隔添加到堆栈中。

If the start time is greater than the end time of the element at the top of the stack, add the interval to the stack.

如果开始时间比在堆栈的顶部元件的结束时间越小，更新元素的结束时间在堆栈的顶部以匹配新元素的结束时间。

If the start time is smaller than the end time of the element at the top of the stack, update the end time of the element at the top of the stack to match the end time of the new element.

在整个数组处理所产生的堆栈应该包含合并的时段。

When the whole array is processed the resulting stack should contain the merged intervals.

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

    }
}

这篇关于算法：合并重叠段的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！