nomadicdude
BAN USERpublic class IntervalTreeAlternate {
TreeSet<Interval> intervals = new TreeSet<>();
public void addInterval(Interval interval) {
intervals.add(interval);
}
//variation of above
public boolean isOverlapping(int low1, int high1, int low2, int high2) {
return low1 <= high2 && low2 <= high1;
}
//returns all overlaps
public ArrayList<List<Interval>> findAllOverlappingIntervals() {
ArrayList<List<Interval>> overlaps = new ArrayList<>();
Iterator<Interval> iterator = intervals.iterator();
try {
Interval min = intervals.first();
Interval successor = intervals.higher(min);
while (successor != null && min != null) {
//create a list for each set of overlapping intervals
List<Interval> overlap = new LinkedList<>();
overlap.add(min);
while (successor != null && isOverlapping(min.low, min.high, successor.low, successor.high)) {
//add the successor to the overlap list
overlap.add(successor);
//the min is now the successor
min = successor;
//check the next successor (for overlaps)
successor = intervals.higher(successor);
}
if (overlap.size() > 0) {
overlaps.add(overlap);
}
//is out of the loop either because there was no overlap or because
min = successor;
successor = intervals.higher(min);
}
} catch (NoSuchElementException ex) {
//in practice we would do something special here...
} catch (NullPointerException ex1) {
//in practice we would do something special here...
}
return overlaps;
}
public void mergeOverlaps() {
ArrayList<List<Interval>> overlaps = findAllOverlappingIntervals();
for (List<Interval> l : overlaps) {
if (l.size() > 1)
mergeOverlaps(l);
}
}
private void mergeOverlaps(List<Interval> overlaps) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < overlaps.size(); i++) {
if (min > overlaps.get(i).low)
min = overlaps.get(i).low;
if (max < overlaps.get(i).high)
max = overlaps.get(i).high;
//remove this element from the interval tree
intervals.remove(overlaps.get(i));
}
//add the merged interval
intervals.add(new Interval(min, max));
}
}
- nomadicdude May 23, 2017