# Minimum Time to Complete All Tasks
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-time-to-complete-all-tasks)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-complete-all-tasks
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack
**Companies:** [Snap](https://scaleengineer.com/companies/snap)
---
## Problem
There is a computer that can run an unlimited number of tasks **at the same time**. You are given a 2D integer array `tasks` where `tasks[i] = [starti, endi, durationi]` indicates that the `ith` task should run for a total of `durationi` seconds (not necessarily continuous) within the **inclusive** time range `[starti, endi]`.

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

Return _the minimum time during which the computer should be turned on to complete all tasks_.

**Example 1:**

**Input:** tasks = [[2,3,1],[4,5,1],[1,5,2]]
**Output:** 2
**Explanation:** 
- 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.

**Example 2:**

**Input:** tasks = [[1,3,2],[2,5,3],[5,6,2]]
**Output:** 4
**Explanation:** 
- 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.

**Constraints:**

* `1 <= tasks.length <= 2000`
* `tasks[i].length == 3`
* `1 <= starti, endi <= 2000`
* `1 <= durationi <= endi - starti + 1 `

# Approaches
## Greedy Approach with Linear Scan
This approach uses a greedy strategy. The core idea is that to minimize the total on-time, we should try to make each second of 'on' time as useful as possible. A time slot is more useful if it can satisfy the requirements of multiple tasks. By processing tasks sorted by their end times, we can make locally optimal choices that lead to a globally optimal solution. When we need to turn on the computer for a task, we choose the latest possible time slots within its interval. This maximizes the chance that these 'on' times will also be useful for subsequent tasks, since subsequent tasks have even later end times.
**Time:** O(N * M + N log N), where N is the number of tasks and M is the maximum end time. Sorting takes `O(N log N)`. The main loop iterates N times. Inside, checking for covered duration and filling needed slots can take up to `O(M)` time in the worst case for each task. · **Space:** O(M), where M is the maximum possible end time (2000 in this case). This space is used to store the `timeOn` array.
**Pros:** Correct and guaranteed to find the optimal solution.; Relatively straightforward to implement.
**Cons:** The time complexity of `O(N * M)` can be slow if both `N` and `M` are large (e.g., close to 2000), potentially leading to a 'Time Limit Exceeded' error on some platforms.
### Explanation
The algorithm begins by sorting the tasks based on their end times in ascending order. This is a common heuristic in interval-based problems that helps in making greedy choices. We use a boolean array, let's call it `timeOn`, to keep track of which time points the computer is turned on. The size of this array will be determined by the maximum possible end time (2000 in this problem). We iterate through the sorted tasks one by one. For each task `[start, end, duration]`, we first determine how much of its required duration is already covered by the time slots we've already decided to turn on. This is done by scanning the `timeOn` array from `start` to `end` and counting the `true` values. If the covered duration is less than the required `duration`, we need to turn on additional time slots. To make a greedy choice, we turn on the latest available time slots within the task's interval `[start, end]`. We iterate backwards from `end` to `start`. For each time `t`, if `timeOn[t]` is `false`, we set it to `true` and decrement the count of needed slots. We repeat this until the task's duration requirement is met. A counter variable keeps track of the total number of `true` values in `timeOn`, which is the final answer.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int findMinimumTime(int[][] tasks) {
        // Sort tasks by their end times
        Arrays.sort(tasks, Comparator.comparingInt(a -> a[1]));

        // The maximum possible time is 2000. We use a 1-based index for time.
        boolean[] timeOn = new boolean[2001];
        int totalTime = 0;

        for (int[] task : tasks) {
            int start = task[0];
            int end = task[1];
            int duration = task[2];

            // 1. Check how much duration is already covered
            int covered = 0;
            for (int t = start; t <= end; t++) {
                if (timeOn[t]) {
                    covered++;
                }
            }

            // 2. If not enough, turn on more slots
            if (covered < duration) {
                int needed = duration - covered;
                // 3. Greedily choose the latest available slots
                for (int t = end; t >= start && needed > 0; t--) {
                    if (!timeOn[t]) {
                        timeOn[t] = true;
                        needed--;
                        totalTime++;
                    }
                }
            }
        }
        return totalTime;
    }
}
```
### Algorithm
*   Sort the `tasks` array based on the `end_i` value in ascending order.
*   Create a boolean array `timeOn` of size 2001 (based on constraints), initialized to `false`. This array will track at which time points the computer is on.
*   Initialize a counter `totalTime = 0`.
*   Iterate through each task `[start, end, duration]` in the sorted array.
*   For the current task, count how many time slots are already `on` within its interval `[start, end]`. Let this be `coveredDuration`. This is done by iterating from `start` to `end` and checking `timeOn`.
*   If `coveredDuration < duration`, the task needs `needed = duration - coveredDuration` more time slots.
*   To satisfy this, iterate backwards from `end` down to `start`. For each time `t` in this range:
    *   If `timeOn[t]` is `false`, set it to `true`, increment `totalTime`, and decrement `needed`.
    *   Stop when `needed` becomes 0.
*   After iterating through all tasks, `totalTime` will hold the minimum total time the computer is on.

## Optimized Greedy Approach with Fenwick Tree
This approach builds upon the same greedy strategy as the first one (sorting by end times) but significantly improves its performance. The bottleneck in the naive approach is the repeated linear scan of time intervals to count how many slots are already active. This can be optimized by using a data structure that can perform range sum queries efficiently. A Fenwick Tree (also known as a Binary Indexed Tree) is an excellent candidate for this, reducing the time to count active slots from `O(M)` to `O(log M)`, where `M` is the maximum time.
**Time:** O(N log N + (N + TotalTime) * log M). Sorting is `O(N log N)`. For each of N tasks, we do one `O(log M)` query. The total number of updates across all tasks is `TotalTime` (the final answer), and each update takes `O(log M)`. Since `TotalTime <= M`, the complexity is bounded by `O(N log N + (N+M)log M)`. This is significantly better than `O(N*M)`. · **Space:** O(M), where M is the maximum end time. This space is for the `timeOn` array and the Fenwick Tree.
**Pros:** Much more efficient time-wise for large N and M.; Follows the same proven greedy logic.
**Cons:** More complex to implement due to the requirement of a Fenwick Tree or a similar data structure.
### Explanation
The overall greedy algorithm remains unchanged: sort tasks by their end times and for each task, satisfy its duration by greedily picking the latest available time slots. We use two structures to track the state: a `boolean[] timeOn` array for `O(1)` lookup of whether a specific time slot is active, and a `FenwickTree` to quickly calculate the number of active slots in any given range `[start, end]`. After sorting tasks by `end` time, we iterate through them. For a task `[start, end, duration]`, we first calculate `covered` slots using the Fenwick Tree: `covered = fenwickTree.query(end) - fenwickTree.query(start - 1)`. This is an `O(log M)` operation. If `covered < duration`, we need to activate `needed = duration - covered` more slots. We iterate backwards from `t = end` down to `start`, using the `timeOn` array to find an inactive slot. When we find one, we activate it by setting `timeOn[t] = true`, updating the Fenwick Tree (`fenwickTree.update(t, 1)`), and decrementing `needed`. The total number of updates to the Fenwick Tree across all tasks is equal to the final answer, leading to a much better time complexity.

```java
// Conceptual code assuming FenwickTree class exists
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int findMinimumTime(int[][] tasks) {
        Arrays.sort(tasks, Comparator.comparingInt(a -> a[1]));

        boolean[] timeOn = new boolean[2001];
        // A Fenwick Tree would be used here for optimization.
        // FenwickTree ft = new FenwickTree(2001);
        int totalTime = 0;

        for (int[] task : tasks) {
            int start = task[0];
            int end = task[1];
            int duration = task[2];

            // In an optimized solution, this part would use the Fenwick tree.
            // int covered = ft.query(end) - ft.query(start - 1);
            // For now, we simulate the logic which is bottleneck.
            int covered = 0;
            for(int i = start; i <= end; i++) {
                if(timeOn[i]) covered++;
            }

            if (covered < duration) {
                int needed = duration - covered;
                totalTime += needed;
                for (int t = end; t >= start && needed > 0; t--) {
                    if (!timeOn[t]) {
                        timeOn[t] = true;
                        // ft.update(t, 1); // Update would happen here
                        needed--;
                    }
                }
            }
        }
        return totalTime;
    }
}
// Assume FenwickTree class is implemented elsewhere
// class FenwickTree { ... }
```
### Algorithm
*   Sort `tasks` by `end_i` in ascending order.
*   Initialize a `boolean[] timeOn` for O(1) lookups and a `FenwickTree ft` of size `M+1` for range queries.
*   Initialize `total_time = 0`.
*   For each task `[start, end, duration]` in sorted `tasks`:
    *   Calculate `covered = ft.query(end) - ft.query(start - 1)`.
    *   Calculate `needed = duration - covered`.
    *   If `needed > 0`:
        *   Iterate `t` from `end` down to `start`:
            *   If `needed == 0`, break the inner loop.
            *   If `!timeOn[t]`:
                *   Set `timeOn[t] = true`.
                *   Update the Fenwick Tree: `ft.update(t, 1)`.
                *   Increment `total_time`.
                *   Decrement `needed`.
*   Return `total_time`.

# Solutions
### Java

```java
class Solution {
public
  int findMinimumTime(int[][] tasks) {
    Arrays.sort(tasks, (a, b)->a[1] - b[1]);
    int[] vis = new int[2010];
    int ans = 0;
    for (var task : tasks) {
      int start = task[0], end = task[1], duration = task[2];
      for (int i = start; i <= end; ++i) {
        duration -= vis[i];
      }
      for (int i = end; i >= start && duration > 0; --i) {
        if (vis[i] == 0) {
          --duration;
          ans += vis[i] = 1;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findMinimumTime(vector<vector<int>> &tasks) {
    sort(tasks.begin(), tasks.end(),
         [&](auto &a, auto &b) { return a[1] < b[1]; });
    bitset<2010> vis;
    int ans = 0;
    for (auto &task : tasks) {
      int start = task[0], end = task[1], duration = task[2];
      for (int i = start; i <= end; ++i) {
        duration -= vis[i];
      }
      for (int i = end; i >= start && duration > 0; --i) {
        if (!vis[i]) {
          --duration;
          ans += vis[i] = 1;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int: tasks . sort(key=lambda x: x[1]) vis = [0] * 2010 ans = 0 for start, end, duration in tasks: duration -= sum(vis[start: end + 1]) i = end while i >= start and duration > 0: if not vis[i]: duration -= 1 vis[i] = 1 ans += 1 i -= 1 return ans

```