https://leetcode.cn/contest/weekly-contest-336/problems/minimum-time-to-complete-all-tasks/
这题我自己想的是一种很朴素的贪心算法:每次只考虑一个时间点,看这个时间点上有多少任务在上面,选择最对任务的时间点。
代码写出来也不是很复杂,但是我不明白为什么这种贪心有问题。注意下面是错误的答案,这个是我认为正确的写法。
class Solution:
def findMinimumTime(self, tasks: List[List[int]]) -> int:
S = min((x[0] for x in tasks))
E = max((x[1] for x in tasks))
N = (E - S + 1)
TS = set(range(S, E + 1))
ans = 0
while tasks:
ev = []
for s, e, d in tasks:
ev.append((s, 0))
ev.append((e + 1, 1))
for t in TS:
ev.append((t, 2))
ev.sort()
d = 0
dm, tm = 0, 0
for ts, ty in ev:
if ty == 0:
d += 1
elif ty == 1:
d -= 1
else:
if d > dm:
dm = d
tm = ts
# print('use tm ', tm)
TS.remove(tm)
ans += 1
tmp = []
for s, e, d in tasks:
if s <= tm <= e:
d -= 1
if d > 0:
tmp.append((s, e, d))
else:
tmp.append((s, e, d))
tasks = tmp
return ans
看了讨论区里面的解法,还是针对右端进行排序,从最右侧开始安排任务。
我们按照截止时间进行排序,那么我们依次考虑每个事件。为了让其更多地与其他任务共同执行,我们应该 贪心地拖延其完成时间,因为后面的任务截止时期必然比其更靠后,前面的任务只需要贪心往后取运行时间即可。
class Solution:
def findMinimumTime(self, tasks: List[List[int]]) -> int:
run = [False] * 2001
tasks.sort(key=lambda x: x[1])
for s, e, d in tasks:
d -= sum(run[s:e + 1]) # 这段时间内之前已经被安排了多少,这个可以附带上
if d > 0:
for t in reversed(range(s, e + 1)): # 剩余的时间从后往前安排
if run[t]: continue
d -= 1
run[t] = True
if d == 0: break
return sum(run)