Finding the max subset of non-overlapping intervals
I see three points of improvement:


The isEmpty check is redundant can be removed. The contains will handle the scenario your are checking for.
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.
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.