範圍分裂問題

Question

夥計，

很久以前就聽說過這個問題。考慮發佈它，以獲得一些觀點，例如使用一些構建或其他有效手段（專門化樹木可能是這樣）

給定一對成對的範圍（5,18）（12,23）（ 15,30）

將它們分成所有可能的子範圍，這些子範圍與集合中的其他範圍重疊。 像（5,11）（12,14），（15,18），（19,23），（24,30）

感謝所有，認識到...

拉詹...

PS是這個AA標準問題，如果是的話，想恩知道它的名字

Answer 1

查所有範圍的端點到一個列表中，但它們標記爲啓動/端點。

[(5, S), (18, E), (12, S), (23, E), (15, S), (30, E)] 

按位置對它們進行排序，通過在結束點之前放置開始點來打破關係。

[(5, S), (12, S), (15, S), (18, E), (23, E), (30, E)] 

然後，您可以通過遍歷此列表來計算範圍，記錄到目前爲止我們處理了多少個起點 - 終點。如果我們看到一個起點，那是一個新的輸出範圍的開始。如果我們的數字是積極的，我們必須首先結束當前範圍。如果我們看到一個終點，則結束當前範圍。

Answer 2

好的，經過一番修補之後，我能夠實現一個顯然工作的版本。因此，對於那些正在尋找一個可行的解決方案，這裏是我的：

private static class RangeVal implements Comparable<RangeVal> { 
    public final BigInteger value; 
    public int count; 

    public RangeVal(BigInteger value, int count) { 
     super(); 
     this.value = value; 
     this.count = count; 
    } 

    @Override 
    public String toString() { 
     return value + (isStart() ? "S" : "E") + count; 
    } 

    @Override 
    public int compareTo(RangeVal o) { 
     // Sort by value first 
     int v = value.compareTo(o.value); 
     if (v != 0) 
      return v; 
     // Then sort Starts before ends 
     return -count; 
    } 

    public boolean isStart() { 
     return count > 0; 
    } 

} 

/** 
* Sort a List of ranges by their number, then start/end and merge multiple 
* start/ends 
* 
* @param temp 
*   a list of RangeVal which can be unsorted 
*/ 
private static void preSort(List<RangeVal> temp) { 
    Collections.sort(temp); 
    RangeVal last = null; 
    for (Iterator<RangeVal> iterator = temp.iterator(); iterator.hasNext();) { 
     RangeVal rangeVal = iterator.next(); 
     if ((last != null) && last.value.equals(rangeVal.value) && (last.isStart() == rangeVal.isStart())) { 
      iterator.remove(); 
      last.count += rangeVal.count; 
     } else 
      last = rangeVal; 
    } 
} 

/** 
* Splits a list into ValueRange Objects that do not overlap each other, but 
* fully represent the ranges given by value 
* 
* @param value 
*   a list of RangeVal Objects that need to be split 
* @return 
*/ 
private static SortedSet<ValueRange> split(List<RangeVal> value) { 
    preSort(value); 
    SortedSet<ValueRange> res = new TreeSet<ValueRange>(); 
    int count = 0; 
    BigInteger start = null; 
    for (RangeVal rangeVal : value) { 
     count += rangeVal.count; 
     if (rangeVal.isStart()) { 
      if (start != null) { 
       //If there was an unended start, then we have to end it just one before the new start 
       res.add(new ValueRange(start, rangeVal.value.subtract(BigInteger.ONE))); 
      } 
      //Set the start to the current Element 
      start = rangeVal.value; 
     } else { 
      //End the current range at this Element 
      res.add(new ValueRange(start, rangeVal.value)); 
      if (count > 0) { 
       //If we expect another end later, the element following this will have to start one after 
       start = rangeVal.value.add(BigInteger.ONE); 
      } else 
       //No new range anymore 
       start = null; 
     } 
    } 
    return res; 
} 

public static void main(String[] args) { 
    // 5->8 9->10 11 
    System.out.println(split(createRanges(5, 8, 9, 10, 11, 11))); 
    // 5, 6->7, 8, 9, 10 
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9))); 
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9))); 
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9, 6, 11, 8, 9))); 
    System.out.println(split(createRanges(5, 10, 6, 8, 8, 9, 6, 9, 6, 11, 8, 9, 14, 18))); 
} 

private static List<RangeVal> createRanges(int... r) { 
    List<RangeVal> temp = new LinkedList<RangeVal>(); 
    for (int i = 0; i < r.length; i++) { 
     temp.add(new RangeVal(BigInteger.valueOf(r[i]), (i % 2) == 0 ? 1 : -1)); 
    } 
    System.out.println("HDLSimulator.createRanges()" + temp); 
    return temp; 
} 

Answer 3

也許我失去了一些東西，但是這似乎是一個簡單的解決方案： 拋出所有的數字在C++ STL容器集。它們將按照升序自動排序。所以他們會以這種方式讀出： 5,12,15,18,23,30 所以，如果你可以容忍重疊，那麼： （5,12）（12,15）（15,18），（18， 23）（23,30）是通過重複每個數字兩次構成的範圍，期望第一個和最後一個，然後分組兩個數字。

如果您無法容忍重疊，則可以通過將增加的數字放在列表中而不是重複它來構造範圍。