First sort the intervals in descending order by their lower bound, breaking ties in increasing order of their upper bounds. Let ~dp(I)~ be the length of the longest sequence starting with interval ~I~.

We can see that ~dp(I) = \max\{1+dp(J)~, for each interval ~J~ completely contained in interval ~I\}~. If ~I~ does not contain any other intervals, then ~dp(I) = 1~.

Because of how we sorted the intervals, interval ~I~ cannot contain interval ~J~ if ~I < J~. A direct implementation of the above idea has time complexity ~\mathcal O(N^2)~ and does not get all points.

To efficiently calculate ~dp(I)~, we introduce a new array of integers ~A~ containing ~1\,000\,000~ elements and initialized to zero. The value ~A(hi)~ tells us the length of the longest sequence starting with an interval whose upper bound is exactly ~hi~.

Now the relation ~dp(I = [lo, hi])~ can be expressed as ~dp(I) = \max\{1+A(x), \text{for }lo \le x \le hi\}~. In other words, we find the length of the longest sequence whose upper bound is inside ~I~. Again, the lower bound of that interval will also be within ~I~, because the intervals are processed in descending order of lower bounds.

Finally, to efficiently find the largest element in the subsequence of ~A~ with indices ~[lo, hi]~, we can use an interval tree or Fenwick tree.