最佳算法找到交點和範圍的重疊，並存儲所得到的範圍內設定

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-65,65-80和75-90我想單獨存儲55-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")); 

Answer 2

使用來自Guava一個RangeSet。

從文檔：

實現，選擇支持add(Range)操作需要忽略空的範圍和聚結連接範圍。

應用到您的例子：

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 3

我認爲範圍可能不總是按順序。當然，代碼可能不是最好的，但如果間隔由起始位置整理它的功能

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

    } 
}