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

Question

假设我有范围

1. 1-10
2. 20-40
3. 30-50
4. 55-65
5. 65-80
6. 75-90
7. 95-100

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

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

所以结果集会是这样的

1. 1-10
2. 20-50
3. 55-90
4. 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

如果区间是按起始位置排序的，有一个非常简单的线性算法来合并区间。排序需要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"));