飞机票： http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=21663

题意：就是给你n个需要处理的事情，第i个必须在li~ri完成，且数量是wi，完成时最大的速度最小是多少；

分析：求最大的速度最小我们可以使用二分来选择速度，但是怎么判断呢？果然还是太菜；其实可以根据时间来判断；具体怎么判断，时间递增，假设当前是j，则把所有左端点小于等于j的都压入到队列中，且按右端点排序（why?因为右端点越大我们可以在后面处理，所以这里贪心的想法），然后设当前还可以处理now个任务，当前碰到的是i，且任务数是w，我们可以判断下now和i的大小，把now和i都减去小的那个，如果now==0了，则退出了，因为不能再处理任务了，如果w不等于0则还没处理完，在压入到队列里。。。没一次j处理玩，可以判断下，如果最小的那个没处理完的r<=j则表明速度太小，返回false（why？？）因为下面大于j的时候已经不能处理它了，如果队列空了，且处理完了那么返回true，你懂得。。。。起先没有想到，，，太渣了。还是看别人的才反映过来。。。啪啪啪，就可以AC了~

/*
Author:Chieh
Because Of You
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define LL long long
using namespace std;
const int maxn=12345;
struct he
{
    int l,r,w;
    bool operator <(const he &a)const
    {
        return r > a.r;
    }
} JLJ[maxn];
priority_queue<he> q;
bool cmp(he a,he b)
{
    return a.l<b.l;
}
int n;
void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d%d",&JLJ[i].l,&JLJ[i].r,&JLJ[i].w);
    }
}
bool check(int x)
{
    int i = 1, j = 0;
    while (!q.empty())
        q.pop();
    while (1)
    {
        while (i <= n && JLJ[i].l <= j)
            q.push(JLJ[i++]);
        int now = x;
        while (now != 0 && !q.empty())
        {
            he temp = q.top();
            q.pop();
            int m = min(now,temp.w);
            now -= m;
            temp.w -= m;
            if (temp.w != 0)
                q.push(temp);
        }
        j++;
        if (!q.empty() && q.top().r <= j)
            return false;
        if (q.empty() && i ==n+1)
            return true;
    }
}
void play()
{
    sort(JLJ+1,JLJ+1+n,cmp);
    int l=1;
    int r=1000000000;
    int MIN=r;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {

            r=mid-1;
            MIN=min(mid,MIN);
        }
        else
        {
            l=mid+1;
        }
    }
    printf("%d\n",MIN);
}
int T;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    // cout << "Hello world!" << endl;
    return 0;
}