2589. Minimum Time to Complete All Tasks LeetCode Solution

In this guide, you will get 2589. Minimum Time to Complete All Tasks LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Complete All Tasks problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Time to Complete All Tasks solution in C++
4. Minimum Time to Complete All Tasks solution in Java
5. Minimum Time to Complete All Tasks solution in Python
6. Additional Resources

Problem Statement of Minimum Time to Complete All Tasks

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

Complexity Analysis

• Time Complexity: O(n^2)
• Space Complexity: O(2000) = O(1)

2589. Minimum Time to Complete All Tasks LeetCode Solution in C++

class Solution {
 public:
  int findMinimumTime(vector<vector<int>>& tasks) {
    constexpr int kMax = 2000;
    vector<bool> running(kMax + 1);

    // Sort tasks by end.
    sort(
        tasks.begin(), tasks.end(),
        [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });

    for (const vector<int>& task : tasks) {
      const int start = task[0];
      const int end = task[1];
      const int duration = task[2];
      int neededDuration = duration - count(running.begin() + start,
                                            running.begin() + end + 1, true);
      // Greedily run the task as late as possible so that later tasks can run
      // simultaneously.
      for (int i = end; neededDuration > 0; --i) {
        if (!running[i]) {
          running[i] = true;
          --neededDuration;
        }
      }
    }

    return ranges::count(running, true);
  }
};
/* code provided by PROGIEZ */

2589. Minimum Time to Complete All Tasks LeetCode Solution in Java

class Solution {
  public int findMinimumTime(int[][] tasks) {
    final int kMax = 2000;
    boolean[] running = new boolean[kMax + 1];

    // Sort tasks by end.
    Arrays.sort(tasks, (a, b) -> Integer.compare(a[1], b[1]));

    for (int[] task : tasks) {
      final int start = task[0];
      final int end = task[1];
      final int duration = task[2];
      int neededDuration = duration;
      for (int i = start; i <= end; ++i)
        if (running[i])
          --neededDuration;
      // Greedily run the task as late as possible so that later tasks can run
      // simultaneously.
      for (int i = end; neededDuration > 0; --i) {
        if (!running[i]) {
          running[i] = true;
          --neededDuration;
        }
      }
    }

    return (int) IntStream.range(0, running.length)
        .mapToObj(i -> running[i])
        .filter(r -> r)
        .count();
  }
}
// code provided by PROGIEZ

2589. Minimum Time to Complete All Tasks LeetCode Solution in Python

class Solution:
  def findMinimumTime(self, tasks: list[list[int]]) -> int:
    kMax = 2000
    running = [False] * (kMax + 1)

    # Sort tasks by end.
    for start, end, duration in sorted(tasks, key=lambda x: x[1]):
      neededDuration = (duration -
                        sum(running[i] for i in range(start, end + 1)))
      # Greedily run the task as late as possible so that later tasks can run
      # simultaneously.
      i = end
      while neededDuration > 0:
        if not running[i]:
          running[i] = True
          neededDuration -= 1
        i -= 1

    return sum(running)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.