链接：https://vjudge.net/problem/UVA-1422
思路：一开始以为是一道很普通的二分，后面发现没那么简单，因为区间可以重叠，所以要决策每个区间到底要完成哪个任务，然后开始枚举任务，结果反而不能得出正确的结论（如果每两个任务都要比较的话复杂度也会很高），最后看了题解，发现可以枚举时间，一共最多20000分钟，枚举时间即可，将任务按照起始时间进行排序，然后当时间大于等于任务的起始时间时就可以放入完成队列中，然后这一分钟完成的任务应该选择结束时间最早的来完成，如果还有剩余时间则继续完成下一个，否则就减去该分钟的完成量再入队即可，注意如果队首任务的完成时间大于当前枚举时间则返回false，因为这样贪心下来就确定不可能以速度d完成，二分枚举速度d即可（要学会二分+优先队列这种操作啊！！！！！！）
代码：
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int t,n;
struct work{
int s,e,w;
bool operator<(const work &p)const{
return e>p.e;
}
}a[10001];
bool cmp(const work &a1,const work &a2){
return a1.s<a2.s||(a1.s==a2.s&&a1.e<a2.e);
}
bool c(int d){
priority_queue<work> qq;
work now;
int i=0;
for(int j=1;j<=20000;j++){
if(!qq.empty()){
now = qq.top();
if(now.e<j)return false;//如果队首完成时间小于当前枚举时间，返回false
}
while(i<n&&a[i].s+1<=j){//如果下一个任务开始时间小于当前枚举时间，则入队
qq.push(a[i++]);
}
int sum = d;
while(sum&&!qq.empty()){
now = qq.top();
qq.pop();
//选择任务并在这一分钟完成
if(sum<now.w){
now.w-=sum;
sum = 0;
qq.push(now);//若还有剩余则再入队即可
}
else sum-=now.w;
if(i==n&&qq.empty())return true;
}
}
return false;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].w);
}
sort(a,a+n,cmp);
int lb = 1;
int ub = 1e7;
//二分枚举即可
while(ub>lb){
int mid = (ub+lb)/2;
if(c(mid))ub = mid;
else lb = mid+1;
}
printf("%d\n",ub);
}
return 0;
}
