这应该有效。它是 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);
}
}
范围.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);
}
}
范围.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);
}
}