Finding the max subset of non-overlapping intervals

Question

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

Answer 1

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.