Question

2589. Minimum Time to Complete All Tasks

中文文档

Description

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

Solutions

Solution 1: Greedy + Sorting

We observe that the problem is equivalent to selecting $duration$ integer time points in each interval $[start,..,end]$, so that the total number of selected integer time points is minimized.

Therefore, we can first sort $tasks$ in ascending order of end time $end$. Then we greedily make selections. For each task, we start from the end time $end$ and choose the points as late as possible from back to front. This way, these points are more likely to be reused by later tasks.

In our implementation, we can use an array $vis$ of length $2010$ to record whether each time point has been selected. Then for each task, we first count the number of points $cnt$ that have been selected in the interval $[start,..,end]$, and then select $duration - cnt$ points from back to front, while recording the number of selected points $ans$ and updating the $vis$ array.

Finally, we return $ans$.

The time complexity is $O(n \times \log n + n \times m)$, and the space complexity is $O(m)$. Here, $n$ and $m$ are the lengths of $tasks$ and $vis$ array, respectively. In this problem, $m = 2010$.

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

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;
  }
}

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;
  }
};

func findMinimumTime(tasks [][]int) (ans int) {
  sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] })
  vis := [2010]int{}
  for _, task := range tasks {
    start, end, duration := task[0], task[1], task[2]
    for _, x := range vis[start : end+1] {
      duration -= x
    }
    for i := end; i >= start && duration > 0; i-- {
      if vis[i] == 0 {
        vis[i] = 1
        duration--
        ans++
      }
    }
  }
  return
}

function findMinimumTime(tasks: number[][]): number {
  tasks.sort((a, b) => a[1] - b[1]);
  const vis = new Array(2010).fill(0);
  let ans = 0;
  for (let [start, end, duration] of tasks) {
    for (let i = start; i <= end; ++i) {
      duration -= vis[i];
    }
    for (let i = end; i >= start && duration > 0; --i) {
      if (vis[i] === 0) {
        --duration;
        ans += vis[i] = 1;
      }
    }
  }
  return ans;
}