OneDay的游戏

发布时间: 2018年6月14日 17:53   最后更新: 2018年6月14日 17:58   时间限制: 1000ms   内存限制: 256M

OneDay最近在写一个游戏。他需要调用许多第三方库中的函数。

已知函数$i$从第$a_i$个版本中开始支持直到第$b_i$个版本。也就是说从第$b_i+1$个版本开始就不再支持这个函数。

这个库不是免费使用的,但是OneDay想要使用库里面所有的函数,他希望你帮他算算最少要购买哪几个版本的库才可以使用所有的函数。

第一行有一个整数$T$,表示测试数据的组数。
对于每组测试数据,第一行为一个整数$n$,表示函数的个数;
接下来$n$行,每行两个整数$a_i,b_i$,表示函数$i$可用的版本区间。
$T \le 100$
$1 \le n \le 2 \times 10 ^ {5}$
$1 \le a_i \le b_i \le 2 \times 10 ^ {9}, 1 \le i \le n$
$\sum n \le 2 \times 10 ^ {6}$

对于每组测试数据,输出一个整数,表示使用所有函数最少需要购买的库的个数。

复制
1
5
2 4
1 3
2 3
3 6
4 5
2

对于样例,购买第$3$个版本和第$4$个版本的库即可。

basic algorithm

ACM集训队暑期集训热身赛