# 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[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;
}

-
Write tests covering all branches and all border cases. Afterwards you can happily try to merge your if branches and start other optimizations. – mnhg Jan 19 '13 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. – user384706 Jan 20 '13 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.) – mnhg Jan 20 '13 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." – abuzittin gillifirca Jan 21 '13 at 9:38
If you can, I'd also put this method under Pair class, so you have interval.overlaps( selectedIntervals );. – knownasilya Jan 21 '13 at 15:56

I see three points of improvement:

1. The isEmpty check is redundant can be removed. The contains will handle the scenario your are checking for.
2. The Comparator really clutters things up, and since you already have a SortedSet coming in, I know you have another compareTo method somewhere else. If Pair is one of your classes, go ahead and make it implement Comparable so you don't have to worry about rewriting comparison logic everywhere.
3. Your conditional block could be simplified if you only look for your failure cases. In cases like this, I usually step back and start by writing our pseudo code for these complex boolean constructs and let loose with DeMorgan's law.

Here's a pastebin with my changes. It takes you down from 35 loc to 19 loc. http://pastebin.com/NpSHemqP

--edit-- Wrong sleep deprived academic reference.

-
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()? – Dave Jarvis Jan 21 '13 at 17:18
As for that '<=', OP is going to have to weigh in on what actually constitutes an overlap. Actually, I like the Pair.overlaps() proposal @Knownasilya made above. Then one could get free this code from that complexity. – matt.moser Jan 21 '13 at 17:48