【JAVA】有关系数对中两侧均递增的最大对数Pro20210628
题目
哲珉常去的健身房进了一种新的健身器材。该器材是以两柱子竖立的形态，每个柱子上有N+1个把手，各把手都以从下到上的方向贴着0到N的编号。
使用该器材进行锻炼时，需要用左手握住左侧柱子的0号把手，用右手握住右侧柱子的0号把手。然后，将双手向上移动到更高的把手来持续进行锻炼。
该器材附有一张表，表上以成对的形式写着多个左右把手的编号。锻炼者只能同时握住表上写着的一对把手编号。即，若表上有(3, 4)，那么可以同时握住左侧3号把手和右侧4号把手。若表中没有(2, 6)，那么不能同时握住左侧2号把手和右侧6号把手。
哲珉希望通过一次获得最大程度的锻炼，但锻炼量和他同时移动双手的次数成正比。换句话说，当双手移动的次数越多，能达到的锻炼量就越大。
比如说，假设N=10，并且表中的成对编号为 (2, 3)、(1, 1)、(5, 5)、(7, 4)、(6, 8)、(10, 1)。在这种情况下，双手移动次数最多的一种方法是以 (0, 0)、(1, 1)、(2, 3)、(5, 5)、(6, 8) 的顺序握住把手。这时，双手移动的次数为四次，然而锻炼量达到了最大。
请写一个程序，通过接收健身器材的表来计算双手能移动的最大次数。
[限制条件]
1.把手的最大编号N是介于1到1,000,000,000之间。
2.给出的编号成对个数M是介于1到300,000之间。
[输入]
第一行给出测试用例数量T。接着给出T个测试用例。各个用例的第一行给出把手编号的最大值N和成对个数M。接下来通过M行，每行给出一对左右把手的编号。
[输出]
各测试用例的答案按照顺序标准输出。每个测试用例输出“#x”（其中x表示测试用例编号，从1开始），加一个空格（不带引号），输出题目中要求的双手能移动的最大次数。
[输入输出 示例]
(输入)
2
10 6
2 3
1 1
5 5
7 4
6 8
10 1
14 8
8 10
1 2
3 4
2 3
14 13
4 4
9 13
7 9
(输出)
#1 4
#2 6
思路
左右两侧同时长递，那么就先确保一侧递增，再在另一侧求最长递增子序列即可。
所以，先将数对儿的一侧进行升序排序，再在另一侧求最长递增子序列即可。
方法1：IndexTree
// 待上传
方法2：贪心+二分
// 待上传