<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 FenwickTree:
    def __init__(self, n):
        self._n = n
        self._tree = [0] * (n + 1)  # [1..n]

    def update(self, p):
        i = p
        while i <= self._n:
            self._tree[i] += 1
            i += (i & (-i))

    def query(self, p):
        i = p
        res = 0
        while i > 0:
            res += self._tree[i]
            i -= (i & (-i))
        return res

class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        # The target is to maximize the parallelism.
        # We can sort the tasks by ending time and scan the time as the time is in the range of [1, 2000].
        # For each time, we maintain the indices of pending tasks.
        # When we reach a time when there are some tasks to be finished, we greedily consume pending tasks in range [min(start), end] where min(start) refers to the minimum starting time of all the tasks ending with the current time.
        # When we encounter a new ending time, the range of placing compute on events is [min(start), end], hence we should sort starting time from small to large.
        # If there are several tasks with the identical starting time, we want to prioritize the one with more duration so the first task will be consumed lastly.
        # So every time we want to consume the tasks beginning from the current one only if a task has the current time slot. The previous tasks are not to be considered because they should be consumed already.
        tasks.sort(key=lambda x:x[1])
        max_time = tasks[-1][1]
        fwt = FenwickTree(max_time)
        opens = [0] * (max_time + 1)
        for task in tasks:
            # Using segment tree can optimize this as O(logn)
            consumed = fwt.query(task[1]) - fwt.query(task[0] - 1)
            if consumed >= task[2]:
                # The task is already been consumed
                continue
            for i in range(task[1], task[0] - 1, -1):
                if opens[i] == 0:
                    opens[i] += 1
                    fwt.update(i)
                    consumed += 1
                    if consumed == task[2]:
                        break
        return fwt.query(max_time)

244