在Java中簡化範圍

Question

我有一個Range對象，它由min和max組成。因此，可以有如下範圍：

[1, 5] 
[6, 12] 
[13, 14] 

這是我的問題。假設你有一個由

ArrayList<Range> ranges; 

給出的範圍列表，你想解決它們，以便沒有重疊範圍。也就是說，有兩個功能：

public void addRange(Range r); 

public void removeRange(Range r); 

你可以假設每個方法之後，ranges ArrayList中總是會受到最低值排序。請注意，ranges ArrayList始終包含初始範圍[1, 100]。下面是與ranges一些例子前後：

ranges = {[1,5], [6,12], [13,14]} 
addRange([7, 15]) 
ranges = {[1,5], [6,15]} 

ranges = {[1,12], [18,29], [34,89]} 
addRange([16,17]) 
ranges = {{[1,12], [16,17], [18,29], [34,89]} 

ranges = {[16,35]} 
removeRange([19,54]) 
ranges = {[16,19]} 

我怎樣才能寫出這兩個功能？

Answer 1

這應該工作。它是O（n），所以你可能想要替代更快的搜索/排序算法。

DistinctRangeList.java

package range; 

import java.util.LinkedList; 

public class DistinctRangeList { 

    private LinkedList<Range> linkedList; 

    public DistinctRangeList() { 
     linkedList = new LinkedList<Range>(); 
    } 

    public void add(Range newRange) { 
     for (int i = 0; i < linkedList.size(); i++) { 
      Range range = linkedList.get(i); 
      if (range.overlaps(newRange)) { 
       return; 
      } else if (newRange.min < range.min) { 
       linkedList.add(i, newRange); 
       return; 
      } else { 
       continue; 
      } 
     } 
     linkedList.addLast(newRange); 
    } 

    public void remove(Range remove) { 
     for (int i = 0; i < linkedList.size(); i++) { 
      Range range = linkedList.get(i); 
      if (range.equals(remove)) { 
       linkedList.remove(range); 
      } 
     } 
    } 

    public String toString() { 
     String s = ""; 
     for (Range r : linkedList) { 
      s += String.format("[%d, %d] ", r.min, r.max); 
     } 
     return s; 
    } 

    public static void main(String[] args) { 
     DistinctRangeList lst = new DistinctRangeList(); 
     lst.add(new Range(3, 6)); // should add 
     lst.add(new Range(3, 5)); // should not add 
     lst.add(new Range(7, 8)); // should add 
     lst.add(new Range(10, 15)); // should add 
     lst.remove(new Range(10, 15)); 
     lst.add(new Range(10, 12)); // should add 
     lst.add(new Range(1, 2)); // should add to the beginning 
     System.out.println(lst); 
    } 
} 

Range.java

package range; 

public class Range { 
    public int min, max; 

    public Range(int min, int max) { 
     this.min = min; this.max = max; 
    } 

    public boolean equals(Range other) { 
     return this.min == other.min && this.max == other.max; 
    } 

    public boolean overlaps(Range other) { 
     return (min <= other.min && other.min <= max) || 
       (min <= other.max && other.max <= max); 
    } 
} 

---

好吧，我想這是你想要的。 （這是一個有趣的問題，所以我用它往直前。）

RangeSet.java

package range; 

import java.util.LinkedList; 

public class RangeSet { 

    private LinkedList<Range> linkedList; 

    public RangeSet() { 
     linkedList = new LinkedList<Range>(); 
    } 

    public void add(Range range) { 

     System.out.println("Adding " + range + " ..."); 

     if (linkedList.contains(range)) { 
      return; 
     } 

     // First place the new range 
     boolean done = false; 
     for (int i = 0; i < linkedList.size() && !done; i++) { 
      Range current = linkedList.get(i); 
      if (range.min < current.min) { 
       linkedList.add(i, range); 
       done = true; 
      } 
     } 
     if (!done) { 
      linkedList.addLast(range); 
     } 

     // Now, do the necessary merges 
     for (int i = 0; i < linkedList.size() - 1; i++) { 
      Range current = linkedList.get(i); 
      Range next = linkedList.get(i + 1); 
      if (current.overlaps(next)) { 
       current.extendBy(next); 
       linkedList.remove(i + 1); 
      } 
     } 

     System.out.println(this); 
    } 

    public void remove(Range remove) { 

     System.out.println("Removing " + remove + " ..."); 

     for (int i = 0; i < linkedList.size(); i++) { 

      Range current = linkedList.get(i); 

      if (!current.overlaps(remove)) { // no overlap 

       continue; 

      } else if (remove.min <= current.min && remove.max >= current.max) { // the range to remove contains the current node 

       linkedList.remove(i); 

      } else if (remove.min < current.min) { // the range to remove intersects the current node from the left end 

       current.min = remove.max; 

      } else if (remove.max > current.max) { // [...] from the right end 

       current.max = remove.min; 

      } else { // the range to remove is contained within the current node, splitting it in two 

       Range start = new Range(current.min, remove.min); 

       Range end = new Range(remove.max, current.max); 

       linkedList.remove(i); 

       linkedList.add(i, start); 

       linkedList.add(i + 1, end); 
      } 
     } 

     System.out.println(this); 
    } 

    public String toString() { 
     String s = ""; 
     for (Range r : linkedList) { 
      s += r.toString() + " "; 
     } 
     return s; 
    } 

    public static void main(String[] args) { 
     RangeSet set = new RangeSet(); 
     set.add(new Range(3, 6)); 
     set.add(new Range(1, 2)); 
     set.add(new Range(4, 10)); 
     set.add(new Range(50, 100)); 
     set.remove(new Range(9, 90)); 
     System.out.println("Final result:\n" + set); 
    } 
} 

Range.java

package range; 

public class Range { 
    public int min, max; 

    public Range(int min, int max) { 
     this.min = min; this.max = max; 
    } 

    public boolean equals(Range other) { 
     return this.min == other.min && this.max == other.max; 
    } 

    public boolean overlaps(Range other) { 
     return (min <= other.min && other.min <= max) || 
       (min <= other.max && other.max <= max); 
    } 

    public void extendBy(Range other) { 
     if (other.min < this.min) { 
      this.min = other.min; 
     } 
     if (other.max > this.max) { 
      this.max = other.max; 
     } 
    } 

    public String toString() { 
     return String.format("[%d, %d]", min, max); 
    } 
}