C - 最小延迟调度问题.md

C : 最小延迟调度问题

Time Limit: 1 Sec, Memory Limit: 128 Mb

Description

假定有一单个的资源在一个时刻只能处理一个任务。现给定一组任务，其中的每个任务 $i$ 包含一个持续时间 $t_i$ 和截止时间 $d_i$ 。设计与实现一个算法，从 0 时刻开始任务，对这组任务给出一个最优调度方案，使其所有任务中的最大延迟最小化。任务 $i$的延迟指实际完成时间 $f_i$ 减去截止时间 $d_i$

Input

第一行输入一个t，代表有t组样例。（t≤10）

每个样例第一行输入一个n（n≤100），代表工作数，接下来n行，每行输入两个数ti（1≤ti≤100）和di（1≤di≤1000），代表任务持续时间和截止时间。

Output

输出所有任务中的最大延迟的最小值

Sample Input

1
6
3 6
2 8
1 9
4 9
3 14
2 15

Sample Output

1

参考代码