思路:优先队列优化贪心

对于某一时刻，如果同时有三个作业,他们的完成时长为A < B < C.那么一定是先完成A 在完成 B 在完成 C。 这样加和是最小的。

所以对于任意时刻，我们查询优先队列里完成时长最小的作业进行完成即可。

一个问题就是在完成任务的时候，可能会随着时间推移突然出现一个任务D，他的完成时长最小，此时需要切换任务。所以在模拟的时候，当前时间now不是直接 + heap.top() , 而是需要判断一下，如果下一个任务的start_time <= now + heap.top() 并且他具有比当前任务更小的完成时长，则临时切换任务，并把当前任务放回队列中。

python

import heapq

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x: x[0])

queue = []
start = 0
ans = 0
idx = 0

while queue or idx < n:
    if not queue:
        start = max(start, a[idx][0])
    while idx < n and a[idx][0] <= start:
        heapq.heappush(queue, [a[idx][1], idx])
        idx += 1
    if queue:
        next_time = start + queue[0][0]
    if idx < n:
        next_time = min(next_time, a[idx][0])
    curr = heapq.heappop(queue)
    curr[0] -= next_time - start
    if curr[0] == 0:
        ans += next_time - a[curr[1]][0]
    else:
        heapq.heappush(queue, curr)
    start = next_time

print(ans)

多多有很多作业，同时刻他只能做一份作业。一个学期内多多共有 n 份作业，每份作业会在第 ti 时刻布置下来，需要 wi 时间才能完成，多多可以在任意时间改变自己当前的作业（前提是改变后的作业必须在布置且未完成），第 i 份作业的完成耗时为最终完成时刻减去作业被布置的时刻 ti；（详见样例）。问多多应如何分配自己的作业时间，才能使得所有作业的完成耗时总和最短？

输入描述

第一行为一个整数 $n (1 <= n <= 10^5)$，表示有 n 份作业。

接下来 $n$ 行，每行两个整数 $ti, wi (1 <= ti, wi <= 10^9)$，分别表示作业的布置时刻与完成时间。

输出描述

输出一个整数，表示所有作业的最短完成耗时。

样例说明

对于 $50$ 的数据，$1 <= n <= 1000, 1 <= ti, wi <= 10^5$;

对于 100% 的数据，$1 <= n <= 10^5,1 <= ti, wi <= 10^9$;

数据保证对于任意$i∈[1,n - 1]$,都有 $t_i \leq t_{i+1}$

样例1

输入

3
1 5
5 1
7 3

输出

10

说明

-在时刻1到时刻6之间做作业1，作业1开始时刻为1，完成时刻为6，耗时为6-1=5

-时刻6到时刻7做作业2，作业2开始时刻为5，完成时刻为7，耗时为7-5=2

-时刻7到时刻 10 做作业3，作业3开始时刻为7，完成时刻为10，耗时为3

总耗时为 5+2+3=1

样例2

输入

5
1 1
4 2
9 3
16 4
25 5

输出

15