Finding nested intervals efficiently
This problem is as hard as comparison sorting, given n input number sort them.

You can make interval set from input number set $S$ (w.l.o.g suppose input numbers are in $Z^+$) as follow:

$ \Gamma = \{(a,b) \mid a\in S \wedge b=\max_{t\in S} \{2\cdot t - a + 1 \} \}$

Above transformation can be done in $O(n)$.

But if you find a nesting relation in this interval set in $o(n \log n)$, you can sort input array in $o(n \log n)$, But comparison sorting barrier is $\Omega(n \log n)$, So the algorithm which finds interval nesting cannot be better than $\Omega(n \log n)$ with respect to comparision sorting barrier, But also $O(n \log n)$ algorithm is trivial.