java - 将范围列表缩小为整数数组

Question

我有这样的代码

public List<int[]> getMinifiedRanges(List<int[]> ranges) {
    for (int[] range : ranges) {

    }
}

我的目标是压缩范围列表，由包含范围上限和下限的整数数组表示

例如。 [100, 200] [250, 350] - 这个例子会返回相同的输入，因为没有重叠

[100, 200] [150, 350] [400, 500] - 这将返回 [100, 350] [400, 500] 因为第二个范围的下限包含在第一个范围内，所以返回的范围将有它的上限扩展到 350 - 注意当输入是 3 个数组时它如何只返回两个数组。

我无法弄清楚如何从当前范围中检索以前的范围，以便我可以扩展下限或上限。

Answer 1

一旦您对范围进行了排序(按最小值，然后按最大值)，每组重叠范围将被组合在一起，因此您可以遍历列表，检查每个范围与最后合并的范围。

public static List<int[]> getMinifiedRanges(List<int[]> ranges) {
    List<int[]> minRanges = new ArrayList<>();
    if (ranges.isEmpty()) return minRanges;

    List<int[]> sorted = new ArrayList<>(ranges); // don't modify input list
    Collections.sort(sorted, Comparator.<int[]>comparingInt(r -> r[0]).thenComparingInt(r -> r[1]));

    int[] last = sorted.get(0);
    for (int[] next : sorted.subList(1, sorted.size())) {
        if (last[1] < next[0]) {
            minRanges.add(last);
            last = next;
        } else if (next[1] > last[1]) {
            last = new int[] { last[0], next[1] };
        }
    }
    minRanges.add(last);

    return minRanges;
}