java - 算法:合并重叠片段

标签 java arrays algorithm list sorting

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

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

例如,他们代表这种情况: enter image description here

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

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

最佳答案

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

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

将排序好的数组的第一个元素加入栈中,然后对数组中的每个元素,将其与栈顶的元素进行比较

如果开始时间大于栈顶元素的结束时间,则将该区间加入栈中。

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

处理整个数组时,生成的堆栈应包含合并的区间。

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

    }
}

关于java - 算法:合并重叠片段,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32585990/

相关文章:

java - 如何将数据透视查询的用户定义变量(@sql)获取到java的结果集

java - 如何在 Eclipse 中找到抽象方法的实现位置?

algorithm - 如何在不存储两个版本的情况下检查更改了多少数据

java - 无法在泛型类中将 Double 转换为 Float

java - 为什么 Spring Context 会加载两次?

javascript - 从 URLSearchParams 恢复数组时,Object.fromEntries 无法按预期工作?

javascript - 如何将多维传递给javascript并再次以多维形式存储?

Javascript/Typescript - 无法将所有内容映射到表格

xml - 如何从 GPX 文件计算距离?

algorithm - 模算法创建