Лучший алгоритм поиска пересечения и перекрытия диапазонов и хранения результирующего диапазона, установленного

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, представляют собой массивы start и end array.

Мое решение:

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 журнал 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

Используйте RangeSet из Guava.

Из документации:

Реализация, которые выбирают для поддержки 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("--------------------------------------------------------------------------------"); 

    } 
}