Problem

There are N schedules, the i-th schedule has start time si and end time ei (1 <= i <= N). There are some machines. Each two overlapping schedules cannot be performed in the same machine. For each machine the working time is defined as the difference between time_end and time_start , where time_end is time to turn off the machine and time_start is time to turn on the machine. We assume that the machine cannot be turned off between the time_start and the time_end.
Print the minimum number K of the machines for performing all schedules, and when only uses K machines, print the minimum sum of all working times.

Input

The first line contains an integer T (1 <= T <= 100), the number of test cases. Each case begins with a line containing one integer N (0 < N <= 100000). Each of the next N lines contains two integers si and ei (0<=si<ei<=1e9)(0<=si<ei<=1e9).

Output

For each test case, print the minimum possible number of machines and the minimum sum of all working times.

Sample Input

1
3
1 3
4 6
2 5

Sample Output

2 8

思路

贪心。对任务按开始时间排序。选择结束时间小于且最接近当前任务开始时间的机器完成当前任务，如果找不到，就新开一个机器来完成当前任务。需要用到STL中的multiset。

代码

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
const int N=1e5+5;
struct Node{
    int l,r;
    bool operator<(const Node &n)const{
        return l<n.l;
    }
}a[N];
multiset<long long>s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++)cin>>a[i].l>>a[i].r;
        s.clear();
        sort(a,a+n);
        int tot=0;
        long long res=0;
        for(int i=0;i<n;i++){
            if(s.empty()){
                ++tot;
                s.insert(a[i].r);
                res+=a[i].r-a[i].l;
            }
            else{
                auto temp_it=s.upper_bound(a[i].l);
                if(temp_it==s.begin()){
                    ++tot;
                    s.insert(a[i].r);
                    res+=a[i].r-a[i].l;
                }
                else{
                    --temp_it;
                    res+=a[i].r-*temp_it;
                    s.erase(temp_it);
                    s.insert(a[i].r);
                }
            }
        }
        cout<<tot<<" "<<res<<endl;
    }
    return 0;
}