Question

2589. 完成所有任务的最少时间

English Version

题目描述

你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 tasks ，其中 tasks[i] = [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点（但不需要连续）。

当电脑需要运行任务时，你可以打开电脑，如果空闲时，你可以将电脑关闭。

请你返回完成所有任务的情况下，电脑最少需要运行多少秒。

 

示例 1：

输入：tasks = [[2,3,1],[4,5,1],[1,5,2]]
输出：2
解释：
- 第一个任务在闭区间 [2, 2] 运行。
- 第二个任务在闭区间 [5, 5] 运行。
- 第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。
电脑总共运行 2 个整数时间点。

示例 2：

输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
输出：4
解释：
- 第一个任务在闭区间 [2, 3] 运行
- 第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。
- 第三个任务在闭区间 [5, 6] 运行。
电脑总共运行 4 个整数时间点。

 

提示：

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

解法

方法一：贪心 + 排序

我们观察发现，题目相当于在每一个区间 $[start,..,end]$ 中，选择 $duration$ 个整数时间点，使得总共选择的整数时间点最少。

因此，我们可以先对 $tasks$ 按照结束时间 $end$ 从小到大排序。然后贪心地进行选择，对于每一个任务，我们从结束时间 $end$ 开始，从后往前选择尽可能靠后的点，这样这些点更有可能被后面的任务重复利用。

我们在实现上，可以用一个长度为 $2010$ 的数组 $vis$ 记录每个时间点是否被选择过。然后对于每一个任务，我们先统计 $[start,..,end]$ 区间内已经被选择过的点的个数 $cnt$，然后从后往前选择 $duration - cnt$ 个点，同时记录选择的点的个数 $ans$ 以及更新 $vis$ 数组。

最后，我们返回 $ans$ 即可。

时间复杂度 $O(n \times \log n + n \times m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为 $tasks$ 的长度和 $vis$ 数组的长度。本题中 $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;
}