Найти подключения диапазонов в множестве а диапазоны

Question

Допустим, у меня есть следующий набор диапазонов:

1 -> 3 
4 -> 5 
7 -> 8 
13 -> 15 
16 -> 16 

Как я могу получить набор:

1 -> 5 
7 -> 8 
13 -> 16 

Answer 1

Зачем вам нужна библиотека для это? Это не так много кода.

class Range{   
    int start , end; 

    public Range(int start , int end){ 
      this.start = start; 
      this.end = end; 
    } 
} 

public static void join(List<Range> ranges){ 
    //sort the list ascending for easier comparison 
    Collections.sort(ranges , (r1 , r2) -> { 
      if(r1 < r2)return -1; 
      else if(r1 > r2)return 1; 
      else return 0; 
    }); 

    int tmp = 1; //counter for the position in the list 
    while(tmp < ranges.size()){ 
      if(ranges.get(tmp).start < ranges.get(tmp - 1).end){ 
       //the range at position tmp intersects with the previous 
       //one -> replace with the joined ranges 
       Range r = new Range(ranges.get(tmp - 1).start , ranges.get(tmp).end); 
       ranges.remove(tmp); 
       ranges.remove(tmp - 1); 
       ranges.add(r , tmp - 1); 
      }else 
       tmp++;//this pair (tmp - 1/tmp) doesn't intersect -> next pair 
    } 
} 

Answer 2

Я бы, вероятно, использовал наборы. (psudo-код) что-то вроде

pairs = "a -> b \n c -> d \n e -> f" 

, например

listOfPairs = pairs.split("\n") 
_set = new set() 
for k : listOfPairs{ 
    temp = k.split("->") 
    _set += _set(range(temp[1],temp[2])) 
} 

На данный момент мы имеем набор со всеми числами в диапазонах. Теперь нам нужно пройти весь диапазон и определить поддиапазоны.

c = min(_set) 
ans = "" 
while(c <= max(_set)){ 
    if(c in _set && !(c-1 in _set)){ 
     ans += string(c) + "->" 
    } 
    if((c in _set) && !(c+1 in _set)){ 
     ans += string(c) + " \n" 
    } 
} 

Answer 3

Это также может быть реализован с помощью TreeMap которого клавиша начинается диапазон и значение диапазона заканчивается следующим образом:

public class ContinuousRangeSet { 
    private TreeMap<Integer, Integer> ranges = new TreeMap<Integer, Integer>(); 

    public void addRange(int start, int end) { 
     int effectiveStart = start, effectiveEnd = end; 
     Map.Entry<Integer, Integer> previousRange = ranges.floorEntry(start); 
     if (previousRange != null && previousRange.getValue() + 1 >= start) { 
      // the start is in the middle of an existing range 
      effectiveStart = previousRange.getKey(); 
     } 

     SortedMap<Integer,Integer> overlappingRanges = ranges.subMap(start, true, end + 1, true); 
     if (!overlappingRanges.isEmpty()) { 
      Integer lastOverlappingKey = overlappingRanges.lastKey(); 
      if (ranges.get(lastOverlappingKey) > end) { 
       // the end is in the middle of an existing range 
       effectiveEnd = ranges.get(lastOverlappingKey); 
      } 
     } 
     // we don't want to keep the overlapping ranges 
     overlappingRanges.clear(); 

     ranges.put(effectiveStart, effectiveEnd); 
    } 

    public static void main(String[] args) { 
     ContinuousRangeSet rangeSet = new ContinuousRangeSet(); 
     rangeSet.addRange(1, 3); 
     rangeSet.addRange(4, 5); 
     rangeSet.addRange(7, 8); 
     rangeSet.addRange(13, 15); 
     rangeSet.addRange(16, 16); 
     System.out.println(rangeSet.ranges); 

     rangeSet.addRange(3, 14); 
     System.out.println(rangeSet.ranges); 
    } 
} 

Выход:

{1=5, 7=8, 13=16} 
{1=16} 

(уведомления я Бесполезное 't проверить все крайние случаи ...)