<p>There is a computer that can run an unlimited number of tasks <strong>at the same time</strong>. You are given a 2D integer array <code>tasks</code> where <code>tasks[i] = [start<sub>i</sub>, end<sub>i</sub>, duration<sub>i</sub>]</code> indicates that the <code>i<sup>th</sup></code> task should run for a total of <code>duration<sub>i</sub></code> seconds (not necessarily continuous) within the <strong>inclusive</strong> time range <code>[start<sub>i</sub>, end<sub>i</sub>]</code>.</p>

<p>You may turn on the computer only when it needs to run a task. You can also turn it off if it is idle.</p>

<p>Return <em>the minimum time during which the computer should be turned on to complete all tasks</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> tasks = [[2,3,1],[4,5,1],[1,5,2]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
- The first task can be run in the inclusive time range [2, 2].
- The second task can be run in the inclusive time range [5, 5].
- The third task can be run in the two inclusive time ranges [2, 2] and [5, 5].
The computer will be on for a total of 2 seconds.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> tasks = [[1,3,2],[2,5,3],[5,6,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 
- The first task can be run in the inclusive time range [2, 3].
- The second task can be run in the inclusive time ranges [2, 3] and [5, 5].
- The third task can be run in the two inclusive time range [5, 6].
The computer will be on for a total of 4 seconds.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= tasks.length &lt;= 2000</code></li>
	<li><code>tasks[i].length == 3</code></li>
	<li><code>1 &lt;= start<sub>i</sub>, end<sub>i</sub> &lt;= 2000</code></li>
	<li><code>1 &lt;= duration<sub>i</sub> &lt;= end<sub>i</sub> - start<sub>i</sub> + 1 </code></li>
</ul>

class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        mx = max(t[1] for t in tasks)
        # 差分约束
        # 设 a[i] 表示前 i 个时间点中，电脑一共运行了几个时间点
        # a[i + 1] - a[i] >= 0 -> a[i] - a[i + 1] <= 0
        # ∵ duration >= 1
        # a[i + 1] - a[i] <= 1
        # 对于每个任务 [s, e, d], a[e] - a[s-1] >= d -> a[s-1] - a[e] <= -d
        g = [[] for _ in range(mx + 2)]
        for i in range(mx):
            # a[i] - a[i + 1] <= 0
            g[i].append((i + 1, 0))
            # a[i + 1] - a[i] <= 1
            g[i + 1].append((i, 1))
        # a[s-1] - a[e] <= -d
        for s, e, d in tasks:
            g[s - 1].append((e, -d))
        # 差分约束要建立超级源点
        S = mx + 1
        for i in range(mx + 1):
            # 如果 \{a_1,a_2,\dots,a_n\} 是该差分约束系统的一组解，那么对于任意的常数 d，
            # \{a_1+d,a_2+d,\dots,a_n+d\} 显然也是该差分约束系统的一组解，因为这样做差后 d 刚好被消掉
            g[S].append((i, 0))  # g[S].append((i, d))  # d 可以为任意常数

        # SPFA 跑单源最短路 最坏时间复杂度为 O(nm)
        dis = [inf] * (mx + 2)
        vis = [False] * (mx + 2)
        q = deque([S])
        vis[S] = True
        dis[S] = 0
        while q:
            x = q.popleft()
            vis[x] = False
            for y, w in g[x]:
                if dis[y] <= dis[x] + w:
                    continue
                dis[y] = dis[x] + w
                if not vis[y]:
                    q.append(y)
        # 如果 \{a_1,a_2,\dots,a_n\} 是该差分约束系统的一组解，那么对于任意的常数 d，
        # \{a_1+d,a_2+d,\dots,a_n+d\} 显然也是该差分约束系统的一组解，因为这样做差后 d 刚好被消掉
        return dis[0] - dis[mx]
244