# Finding the max subset of non-overlapping intervals

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);
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;
}

• Write tests covering all branches and all border cases. Afterwards you can happily try to merge your if branches and start other optimizations. Jan 19, 2013 at 8:00
• This is my attempt to code a solution to a classic algorithmic problem. I understand how I can write cleaner code. So I don't see how this helps me here. Jan 20, 2013 at 9:33
• Right from looking at the code I had the feeling that there might be some if branches able to be merged to one. I have no time to write some tests and check this. You could also try to minimize your logic with a Karnaugh map. If this is already the minimum amount of conditions, then there is nothing you can do (beside extracting a method or create temporary variable for your conditions to improve the readability.) Jan 20, 2013 at 9:58
• docs.oracle.com/javase/6/docs/api/java/util/… "The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.) The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0." Jan 21, 2013 at 9:38
• If you can, I'd also put this method under Pair class, so you have interval.overlaps( selectedIntervals );. Jan 21, 2013 at 15:56

• Good use of comments. Minor mistake (getStart should be getStart()). And could the last inner if statement be rewritten as return sortedSelections[pos].getStart <= interval.getEnd()? Jan 21, 2013 at 17:18