LC 6318. 完成所有任务的最少时间

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)