题意：
有n个任务， 每个任务要在规定的时间[l, r]内完成， 工作量为 w， 每个任务可以分开完成。
求， 使得所有任务都完成的最大速度的最小值。
思路：
最大值最小问题， 二分。
因为是要完成所有任务， 所以先按开始时间排序， 接下来二分速度。
因为任意两个任务之间的关系只有两种， 1）相交或者包含 2）相切或者相离
如果是情况 2） 那么不需要特殊处理， 按顺序处理过去即可。
如果是情况 1） 那么需要将这个时间段内的任务按照结束时间来进行处理， 结束时间小的优先完成。
然后枚举时间， 从1 开始处理过去， 看是否能处理完所有任务即可。
代码：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 10010
#define MAXM 100
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
struct node
{
int l;
int r;
int t;
int no;
bool operator < (const struct node &y) const
{
return r > y.r;
}
};
int n, sum;
struct node f[MAXN];
int w[MAXN];
bool cmp(const struct node &x, const struct node &y)
{
return x.l == y.l? x.r < y.r : x.l < y.l;
}
void read()
{
sum = ;
scanf("%d", &n);
for(int i = ; i < n; i ++)
{
scanf("%d %d %d", &f[i].l, &f[i].r, &f[i].t);
sum += f[i].t;
f[i].no = i;
}
sort(f, f + n, cmp);
}
bool is_ok(int x)
{
priority_queue <struct node> Q;
for(int i = ; i < n; i ++)
w[f[i].no] = f[i].t;
int i = ;
int pos = ;
while(true)
{
while(i < n && f[i].l <= pos) Q.push(f[i ++]); int ts = x;
while(!Q.empty() && ts)
{
struct node temp = Q.top(); if(temp.r <= pos) return false; w[temp.no] -= ts;
if(w[temp.no] > )
ts = ;
else if(w[temp.no] <= )
{
ts = -w[temp.no];
Q.pop();
}
} if(i == n && Q.empty()) return true;
pos ++;
}
return false;
}
int get_ans()
{
int l = , r = sum;
while(l <= r)
{
int mid = (l + r) / ;
if(is_ok(mid))
r = mid - ;
else
l = mid + ;
}
return l;
} int main()
{
int T;
scanf("%d", &T);
while(T --)
{
read();
printf("%d\n", get_ans());
}
return ;
}