Problem1579--短进程优先调度算法

1579: 短进程优先调度算法

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 16  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

短进程优先(SJF)调度算法从就绪队列中选出运行时间最短的进程交给处理机运行。
现在有n个需要处理的任务,要求使用该算法来进行任务调度。
时间从0开始计时,当处理机空闲时寻找到达时间不超过当前时间且运行时间最短的进程交给处理机运行。
若运行时间相同,则优先处理到达时间早的。
给出这些任务的到达时刻和执行时间(均用分钟表示),请求出这n个任务执行完的时刻。


Input

多组输入。
第一行输入任务数n(1<=n<=1000),
接下来n行每行输入2个整数,代表任务的到达时刻和执行时间。

Output

对于每组输入,输出所有任务执行完的时刻。

Sample Input

4
5 4
1 3
3 7
8 2

Sample Output

2 4
3 11
4 13
1 17

Source/Category