A203.Gold King安排计划

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

干旱最后还是过去了,青青草原又恢复了往日的繁茂,但是干旱也让草原有一部分沙漠化,只有 GoldKingGold King 家的农场,没有丝毫受到影响,大家都想来取经,可是碍于面子,因为 GoldKingGold King 不是那么好说话,于是大家借着来GoldKingGold King 家的小礼堂举办活动之名,借机来参观一下 GoldKingGold King 家的农场。
GoldKingGold King 突然收到很多活动安排,心里也是极高兴的,但是有些活动的时间发生冲突了,这可有些棘手了,每个时间最多安排一个活动,为了尽可能的安排更多的活动,GoldKingGold King 需要好好安排一下这些活动,请问他该如何安排。

输入格式

第一行是一个整型数 mm(0<m<1000<m<100) 表示共有mm组测试数据。 每组测试数据的第一行是一个整数 nn(1<n<100001<n<10000) 表示该测试数据共有 nn 个活动。 随后的 nn 行,每行有两个正整数BiB_i,EiE_i(0Bi,Ei<100000\le B_i,E_i<10000), 分别表示第 ii 个活动的起始与结束时间( BiEiB_i\le E_i )。

输出格式

对于每一组输入,输出最多能够安排的活动数量。每组的输出占一行。

输入输出样例

  • 输入#1

    2
    2
    1 10
    10 11
    3
    1 10
    10 11
    11 20

    输出#1

    1
    2

说明/提示

0<m<1000<m<1001<n<100001<n<100000BiEi<100000\le Bi\le Ei<10000

首页