Skip to content

2589. Minimum Time to Complete All Tasks 👍

  • Time: $O(n^2)$
  • Space: $O(2000) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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) -> 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();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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)