找到范围的交集和重叠并存储结果范围集的最佳算法

Question

我有范围比方说

1-10
20-40
30-50
55-65
65-80
75-90
95-100

在此示例中，20-40 和 30-50 相交而不是同时存储两者，我需要将其存储为 20-50。

然后我想单独存储 55-90，而不是 55-65、65-80 和 75-90。

所以结果集会是这样

1-10
20-50
55-90
95-100

我在 redis 中有这些值，我将它们存储在 Java 中的结构是数组，起始数组和结束数组。

我的解决方案：

for int i =0; i< length-1 ; i++
    for int j=i+1;j<length; j++
        if start[i] <= start[j] && end[i] >= start[j]
            store the min max in start and end array and remove the other two entries and proceed

我发现这是 O(n log n) 是否有更好的算法来做到这一点？

Java 和 redis 中的数据结构以及处理此问题的方法或算法中的任何建议都很棒。

谢谢

Answer 1

使用 RangeSet from Guava.

来自文档：

Implementations that choose to support the add(Range) operation are required to ignore empty ranges and coalesce connected ranges.

应用于您的示例：

public static void main(String args[]) {
    final RangeSet<Integer> ranges = TreeRangeSet.create();
    ranges.add(Range.closed(1, 10));
    ranges.add(Range.closed(20, 40));
    ranges.add(Range.closed(30, 50));
    ranges.add(Range.closed(55, 65));
    ranges.add(Range.closed(65, 80));
    ranges.add(Range.closed(75, 90));
    ranges.add(Range.closed(95, 100));

    System.out.println(ranges);
}

输出：

[[1‥10], [20‥50], [55‥90], [95‥100]]

因为 Range 和 TreeRangeSet 都 implements Serializable 您可以将它们按原样保存到 Redis。

Answer 2

我认为范围可能并不总是有序的。当然，代码可能不是最好的，但它是功能性的

import java.util.*;


class Interval {
    int lo;
    int hi;
    Interval() {
        lo = 0;
        hi = 0;
    }

    Interval(int lo, int hi) {
        this.lo = lo;
        this.hi = hi;
    }

    @Override
    public String toString() {
        return "[" + lo + "," + hi + "]";
    }
}

public class Demo {
    public static ArrayList<Interval> merge(ArrayList<Interval> list) {
        Collections.sort(list, new Comparator<Interval>() {
            public int compare(Interval i1, Interval i2) {
                if (i1.lo == i2.lo) {
                    return i1.hi - i2.hi;
                }
                return i1.lo - i2.lo;
            }
        });
        System.out.println("Sorted Input: " + list);

        ArrayList<Interval> result = new ArrayList<Interval>();
        Interval prev = list.get(0);
        result.add(prev);
        for (int i = 1; i < list.size(); i++) {
            Interval current = list.get(i);
            if (prev.hi >= current.lo) {
                Interval Interval = new Interval(prev.lo, Math.max(prev.hi, current.hi));
                prev = Interval;
            } else {
                prev = current;
            }
            removeIfExist(result, prev);
            result.add(prev);
        }
        return result;
    }

    private static void removeIfExist(ArrayList<Interval> result, Interval prev) {
        if (result.size() > 0) {
            Interval existing = result.get(result.size() - 1);
            if (existing.lo == prev.lo) {
                result.remove(result.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        ArrayList<Interval> list = new ArrayList<Interval>();
        System.out.println("--------------------------------------------------------------------------------");
        list.add(new Interval(30, 50));
        list.add(new Interval(20, 40));
        list.add(new Interval(75, 90));
        list.add(new Interval(1, 10));
        list.add(new Interval(95, 100));
        list.add(new Interval(65, 80));
        list.add(new Interval(55, 65));
        System.out.println("Input: " + list);
        System.out.println("merged Interval: " + merge(list));
        System.out.println("--------------------------------------------------------------------------------");

    }
}

Answer 3

如果区间是按起始位置排序的，有一个非常简单的线性算法来合并区间。排序需要O(nlogn)，所以整体时间复杂度是一样的。如果输入没有排序，相信一般算法还是取O(nlogn)。排序通常更快，因为它与一个小常数相关联。这是更有效的解决方案。

这里是 javascript 中的一个实现，只是为了给你一个想法。您可以翻译成 java 或运行它 node.js:

function merge_intervals(a)
{ // this function save the result IN PLACE
    if (a.length == 0) return;
    var st = a[0][0], en = a[0][1], k = 0;
    for (var i = 1; i < a.length; ++i) {
        if (a[i][0] > en) { // a new interval
            a[k++] = [st, en];
            st = a[i][0], en = a[i][1];
        } else en = a[i][1] > en? a[i][1] : en;
    }
    a[k++] = [st, en]; // add the last interval
    a.length = k; // discard the rest
}

// intervals are half-close-half-open, like C arrays
var a = [[1,10], [20,40], [30,50], [55,65], [65,80], [75,90], [95,100]];
// sort the intervals based on start positions
a.sort(function(x,y) { return x[0]-y[0] });

merge_intverals(a);
for (var i = 0; i < a.length; ++i)
    console.log(a[i].join("\t"));

找到范围的交集和重叠并存储结果范围集的最佳算法

Best algorithm to find intersection and overlapping of ranges and storing the resultant range set

java

algorithm

redis

intersection

overlap