链接：https://ac.nowcoder.com/acm/problem/210102
来源：牛客网
题号：NC210102
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64 位 IO 格式：%lld

题目描述

作为成熟的商人，农夫约翰意识到他必须有效地管理自己的时间。他有 N 份工作，编号为 1..N (1 <= N <= 1,000) 来完成（比如挤奶、打扫谷仓、修补栅栏等等）。为了有效地管理他的时间，他创建了一份必须完成的工作清单。作业 i 需要一定的时间 T_i (1 <= T_i <= 1,000) 才能完成，而且必须在时间 S_i (1 <= S_i <= 1,000,000) 之前完成。农夫约翰在时间 t=0 开始他的一天，并且一次只能完成一项工作，直到完成。即使是成熟的商人也喜欢晚睡；帮助 Farmer John 确定他可以开始工作并仍能按时完成所有工作的最晚时间。

N个工作,每个工作其所需时间,及完成的Deadline,问要完成所有工作,最迟要什么时候开始.

输入描述: 

	

		* 第 1 行：单个整数：N
	


	

		* 第 2..N+1 行：第 i+1 行包含两个以空格分隔的整数：T_i 和 S_i

输出描述: 

* 第 1 行：Farmer John 可以开始工作的最晚时间，如果 Farmer John 不能按时完成所有工作，则为 -1。
示例1

输入 

4
3 5
8 14
5 20
1 16

输出 

2
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct job {     int t;     int end;
};
job jobs[1000001];
int n;
bool cmp(job a, job b);
bool ok(int time) {     for(int i = 0; i < n; i++) {         if(jobs[i].t + time <= jobs[i].end)             time += jobs[i].t;         else             return false;     }     return true;
}
int main() {     int r=1000000000, l=1, mid;     int ans=-1;     cin >> n;     for(int i = 0; i < n; i++)         cin >> jobs[i].t >> jobs[i].end;     sort(jobs, jobs+n, cmp);     while(l<=r) {         mid=l+(r-l)/2;         if(ok(mid)) {             ans=mid;             l=mid+1;         } else             r=mid-1;     }     cout<<ans;     return 0;
}
bool cmp(job a, job b) {     return a.end < b.end;
}