Yet Another Segments Subset
Contest: Codeforces Round 661 (Div. 3)
Difficulty rating: 2300
Tags: data structures, dp, graphs, sortings

You are given $$$n$$$ segments on a coordinate axis $$$OX$$$. The $$$i$$$-th segment has borders $$$[l_i; r_i]$$$. All points $$$x$$$, for which $$$l_i \le x \le r_i$$$ holds, belong to the $$$i$$$-th segment.

Your task is to choose the maximum by size (the number of segments) subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one.

Two segments $$$[l_i; r_i]$$$ and $$$[l_j; r_j]$$$ are non-intersecting if they have no common points. For example, segments $$$[1; 2]$$$ and $$$[3; 4]$$$, $$$[1; 3]$$$ and $$$[5; 5]$$$ are non-intersecting, while segments $$$[1; 2]$$$ and $$$[2; 3]$$$, $$$[1; 2]$$$ and $$$[2; 2]$$$ are intersecting.

The segment $$$[l_i; r_i]$$$ lies inside the segment $$$[l_j; r_j]$$$ if $$$l_j \le l_i$$$ and $$$r_i \le r_j$$$. For example, segments $$$[2; 2]$$$, $$$[2, 3]$$$, $$$[3; 4]$$$ and $$$[2; 4]$$$ lie inside the segment $$$[2; 4]$$$, while $$$[2; 5]$$$ and $$$[1; 4]$$$ are not.

You have to answer $$$t$$$ independent test cases.

Input format:
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 3000$$$) — the number of segments. The next $$$n$$$ lines describe segments. The $$$i$$$-th segment is given as two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$), where $$$l_i$$$ is the left border of the $$$i$$$-th segment and $$$r_i$$$ is the right border of the $$$i$$$-th segment.

Additional constraint on the input: there are no duplicates in the list of segments.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$3000$$$ ($$$\sum n \le 3000$$$).

Output format:
For each test case, print the answer: the maximum possible size of the subset of the given set of segments such that each pair of segments in this subset either non-intersecting or one of them lies inside the other one.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
4
4
1 5
2 4
2 3
3 4
5
1 5
2 3
2 5
3 5
2 2
3
1 3
2 4
2 3
7
1 10
2 8
2 5
3 4
4 4
6 8
7 7

Example output:
3
4
2
7

Editorial:
Firstly, let's compress the given borders of segments (just renumerate them in such a way that the maximum value is the minimum possible and the relative order of integers doesn't change). Pretty standard approach.
Now let's do recursive dynamic programming $$$dp_{l, r}$$$. This state stores the answer for the segment $$$[l; r]$$$ (not necessarily input segment!). How about transitions? Firstly, if there is a segment covering the whole segment $$$[l; r]$$$, why don't just take it? It doesn't change anything for us. The first transition is just skip the current left border and try to take the additional answer from the state $$$dp_{l + 1, r}$$$. The second transition is the following: let's iterate over all possible segments starting at $$$l$$$ (we can store all right borders of such segments in some array $$$rg_l$$$). Let the current segment be $$$[l; nr]$$$. If $$$nr \ge r$$$, just skip it (if $$$nr > r$$$ then we can't take this segment into the answer because it's out of $$$[l; r]$$$, and if $$$nr = r$$$ then we can't take it because we considered it already). Then we can take two additional answers: from $$$dp_{l, nr}$$$ and from $$$dp_{nr + 1, r}$$$. Don't forger about some corner cases, like when $$$nr + 1 > r$$$ or $$$l + 1 > r$$$ and something like that.
You can get the answer if you run the calculation from the whole segment.
What is the time complexity of this solution? We obviously have $$$O(n^2)$$$ states. And the number of transitions is also pretty easy to calculate. Let's fix some right border $$$r$$$. For this right border, we consider $$$O(n)$$$ segments in total. Summing up, we get $$$O(n^2)$$$ transitions. So the time complexity is $$$O(n^2)$$$.
P.S. I am sorry about pretty tight ML (yeah, I saw Geothermal got some memory issues because of using map). I really wanted to make it 512MB but just forgot to do that.