问题 5007 --虎哥看电影

5007: 虎哥看电影

时间限制: 3 Sec  内存限制: 128 MB
提交: 141  解决: 59
[提交][状态][命题人:]

题目描述

虎哥去电影城看电影,电影城共有m部电影,第i部电影的开始时间和结束时间分别为si和ei,电影的好看度为ti,其中ti越小表示这部电影越好看。为了不浪费,当虎哥选择了看某部电影时,必须从头到尾全部看完;由于选择的电影不一定在同一放映厅,虎哥选择的两本电影之间必须留有1的时间差用于换放映厅。
现在虎哥想知道,如何安排看电影的顺序,能使得能看上最多部电影。同时,在此基础上,使得所选电影中的好看度最差的电影最好看。

输入

第一行一个正整数T,代表测试数据的组数为T组。
每组数据中,第一行为一个正整数n,代表电影的数量。
接下来n行,每行为三个正整数si,ei,ti,分别电影的开始时间,结束时间和好看程度。
其中1<=T<=20;1<=n<=100,000;1<=si,ei,ti<=2e9。

输出

每组数据输出两个正整数,这两个正整数用空格隔开,分别是最多能选择的电影数和所选电影中的好看度最差的电影最好看的值。
样例输入
Copy
2
4
1 2 6
2 5 7
6 9 11
6 10 12
2
1 1 6
1 2 3
样例输出
Copy
2 11
1 3

提示

来源

 

[提交][状态]