问题 5745 --可爱的整数

5745: 可爱的整数★★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 54  解决: 37
[提交][状态][命题人:]

题目描述

给定n个整数区间(每个整数区间由两个整数leftright表示:leftright分别为区间的下边界和上边界,即整数区间可表示为:[left, right])

定义函数f(x)为整数x属于整数区间的个数(如果x属于区间i[lefti, righti],则显然有:lefti≤x≤righti)。

如果一个整数x比任意其他整数所属的区间个数都多(即对于任意整数y,都有f(x)>f(y)),则该整数即为可爱的整数。

现给我们一个整数k,你的任务是确定是否有可能删除一些(可能是零)整数区间,以使给定的整数k成为可爱的整数?



输入

第一行只有一个整数t(1≤t≤1000):测试用例的数量。

对于每个测试用例:

第一行共有两个整数nk(1≤nk≤50)

接下来共n行,每行两个整数,第i行的两个整数分别为第i区间的下边界lefti和上边界righti,即第i区间为:[lefti, righti]。保证 1≤left≤right≤50

输出

       共t行,每个测试用例一行一个字符串:YES 或者 NO。如果可以通过删除若干个整数区间使得k为可爱的整数,则输出”YES”,否则输出“NO”
样例输入
Copy
4
4 3
1 3
7 9
2 5
3 6
2 9
1 4
3 7
1 3
2 4
3 5
1 4
6 7
5 5
样例输出
Copy
YES
NO
NO
YES

提示

对于第一个测试用例,k=3,共有4个区间:[1,3],[7,9],[2,5][3,6],所有f(3)=3,对于任意其他整数y,都有f(y)<=2, 所以3已经是可爱的整数。

对于测试用例2和测试用例3,我们都无法通过删除一些区间,使得k为可爱的整数;

对于测试用例4k=5,共有3个整数区间:[1,4],[6,7],[5,5],我们可以删除[1,4]区间和[6,7]区间,只保留[5,5]区间,使得f(5)=1, 对于任意其他整数y,都有f(y)=0,此时5是可爱的整数。

来源

 

[提交][状态]