Hard

题目描述

有一台可以同时运行无限个任务的计算机。给你一个二维整数数组 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

解题思路

这是一个贪心算法问题，关键思路是尽可能晚地安排任务执行，这样可以最大化时间重叠利用。

核心策略：

  1. 按结束时间排序：将所有任务按照结束时间升序排列，这样我们可以从最早结束的任务开始处理。

  2. 贪心选择时间点：对于每个任务，我们应该尽可能在其时间窗口的末尾安排执行时间。原因是越晚安排，越有可能与后续任务的时间窗口重叠，从而节省总开机时间。

  3. 动态维护已开机时间：使用一个布尔数组记录每个时间点是否已经开机。对于当前任务，先统计在其时间窗口内已经有多少时间点开机，然后从右到左（从结束时间往开始时间）贪心地选择新的时间点开机，直到满足该任务的持续时间要求。

算法流程：

  1. 将任务按结束时间排序
  2. 维护一个 running 数组表示每个时间点是否开机
  3. 对每个任务，计算已满足的时间，然后从右到左补充不足的时间
  4. 最后统计总开机时间

时间复杂度为 O(n²)，其中 n 是最大时间值，空间复杂度 O(n)。

代码实现

class Solution {
public:
    int findMinimumTime(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        vector<bool> running(2001, false);
        
        for (auto& task : tasks) {
            int start = task[0], end = task[1], duration = task[2];
            
            // Count already satisfied time
            int satisfied = 0;
            for (int i = start; i <= end; i++) {
                if (running[i]) satisfied++;
            }
            
            // Need to schedule more time
            int need = duration - satisfied;
            
            // Greedily choose time slots from right to left
            for (int i = end; i >= start && need > 0; i--) {
                if (!running[i]) {
                    running[i] = true;
                    need--;
                }
            }
        }
        
        int result = 0;
        for (bool run : running) {
            if (run) result++;
        }
        
        return result;
    }
};

class Solution:
    def findMinimumTime(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda x: x[1])
        
        running = [False] * 2001
        
        for start, end, duration in tasks:
            # Count already satisfied time
            satisfied = sum(running[start:end+1])
            
            # Need to schedule more time
            need = duration - satisfied
            
            # Greedily choose time slots from right to left
            for i in range(end, start - 1, -1):
                if need <= 0:
                    break
                if not running[i]:
                    running[i] = True
                    need -= 1
        
        return sum(running)

public class Solution {
    public int FindMinimumTime(int[][] tasks) {
        Array.Sort(tasks, (a, b) => a[1].CompareTo(b[1]));
        
        bool[] running = new bool[2001];
        
        foreach (var task in tasks) {
            int start = task[0], end = task[1], duration = task[2];
            
            // Count already satisfied time
            int satisfied = 0;
            for (int i = start; i <= end; i++) {
                if (running[i]) satisfied++;
            }
            
            // Need to schedule more time
            int need = duration - satisfied;
            
            // Greedily choose time slots from right to left
            for (int i = end; i >= start && need > 0; i--) {
                if (!running[i]) {
                    running[i] = true;
                    need--;
                }
            }
        }
        
        int result = 0;
        foreach (bool run in running) {
            if (run) result++;
        }
        
        return result;
    }
}

var findMinimumTime = function(tasks) {
    tasks.sort((a, b) => a[1] - b[1]);
    
    const running = new Array(2001).fill(false);
    
    for (const [start, end, duration] of tasks) {
        // Count already satisfied time
        let satisfied = 0;
        for (let i = start; i <= end; i++) {
            if (running[i]) satisfied++;
        }
        
        // Need to schedule more time
        let need = duration - satisfied;
        
        // Greedily choose time slots from right to left
        for (let i = end; i >= start && need > 0; i--) {
            if (!running[i]) {
                running[i] = true;
                need--;
            }
        }
    }
    
    return running.filter(run => run).length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × m + n log n)n 是任务数量，m 是最大时间值(2000)，排序 O(n log n)，每个任务遍历时间区间 O(m)
空间复杂度O(m)需要 O(m) 的数组记录每个时间点的状态，m = 2000

相关题目