How could this code become cleaner? I think that the way I handle the interfaces and binary search could be improved. I am trying to understand how to structure such a code (and usage of APIs) in a cleaner and more efficient manner.
This code solves the problem of finding the max subset of non-overlapping intervals. I especially believe the way I handle the binary search result is error-prone.
private boolean nonOverlapping(Pair interval, SortedSet<Pair> selectedIntervals) {
if(selectedIntervals.isEmpty())
return true;
if(selectedIntervals.contains(interval)){
return true;
}
Pair[] sortedSelections = selectedIntervals.toArray(new Pair[0]);
int pos = Arrays.binarySearch(sortedSelections, interval, new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
return o1.getStart() - o2.getEnd();
}
});
pos = (-pos) -1;
if(pos == sortedSelections.length){
if(sortedSelections[pos - 1].getEnd() < interval.getStart()){
return true;
}
}
else if(sortedSelections[pos].getEnd() > interval.getStart()){
if(pos + 1 < sortedSelections.length){
if(sortedSelections[pos + 1].getEnd() < interval.getStart()){
return false;
}
}
if(pos - 1 >= 0){
if(sortedSelections[pos - 1].getEnd() < interval.getStart()){
return false;
}
}
return true;
}
return false;
}
if
branches and start other optimizations. \$\endgroup\$ – mheinzerling Jan 19 '13 at 8:00Pair
class, so you haveinterval.overlaps( selectedIntervals );
. \$\endgroup\$ – knownasilya Jan 21 '13 at 15:56