Medium

题目描述

给你 n 个任务，编号从 0 到 n - 1，由二维整数数组 tasks 表示，其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i 个任务将在 enqueueTimei 时刻变为可用，并且需要 processingTimei 的时间来完成处理。

你有一个单线程 CPU，它一次最多只能处理一个任务，并将按以下方式运行：

  • 如果 CPU 空闲且没有可处理的任务，则 CPU 保持空闲状态。
  • 如果 CPU 空闲且有可用任务，CPU 将选择处理时间最短的任务。如果多个任务有相同的最短处理时间，它将选择索引最小的任务。
  • 一旦任务开始，CPU 将在不停止的情况下处理整个任务。
  • CPU 可以在完成任务后立即开始新任务。

返回 CPU 处理任务的顺序。

示例 1：

输入：tasks = [[1,2],[2,4],[3,2],[4,1]]
输出：[0,2,3,1]
解释：事件按以下顺序发生：
- 时间 = 1，任务 0 可以处理。可用任务 = {0}。
- 同时在时间 = 1，空闲的 CPU 开始处理任务 0。可用任务 = {}。
- 时间 = 2，任务 1 可以处理。可用任务 = {1}。
- 时间 = 3，任务 2 可以处理。可用任务 = {1, 2}。
- 同时在时间 = 3，CPU 完成任务 0 并开始处理任务 2，因为它是最短的。可用任务 = {1}。
- 时间 = 4，任务 3 可以处理。可用任务 = {1, 3}。
- 时间 = 5，CPU 完成任务 2 并开始处理任务 3，因为它是最短的。可用任务 = {1}。
- 时间 = 6，CPU 完成任务 3 并开始处理任务 1。可用任务 = {}。
- 时间 = 10，CPU 完成任务 1 并变为空闲。

示例 2：

输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
输出：[4,3,2,0,1]

提示：

  • tasks.length == n
  • 1 <= n <= 10^5
  • 1 <= enqueueTimei, processingTimei <= 10^9

解题思路

这是一道模拟题，需要按照单线程 CPU 的执行规则来处理任务。

核心思路：

  1. 排序预处理：首先按照任务的入队时间对所有任务进行排序，这样可以按时间顺序处理可用任务。
  2. 优先队列管理可用任务：使用最小堆来存储当前可用的任务，堆的排序规则是：优先处理时间短的任务，处理时间相同时优先索引小的任务。
  3. 时间模拟：维护当前时间，当 CPU 完成一个任务后，需要将所有在当前时间之前入队的新任务加入优先队列。

算法流程：

  • 将任务与其原始索引一起排序
  • 初始化当前时间为 0，使用指针追踪下一个待入队的任务
  • 当还有任务未处理时：
    • 如果优先队列为空且当前时间小于下一个任务的入队时间，则跳转到该任务的入队时间
    • 将所有在当前时间可用的任务加入优先队列
    • 从优先队列中取出最优任务执行，更新当前时间

时间复杂度分析：

  • 排序：O(n log n)
  • 堆操作：每个任务最多入队出队一次，总共 O(n log n)
  • 总体：O(n log n)

代码实现

class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n = tasks.size();
        vector<pair<pair<int, int>, int>> sortedTasks; // {{enqueueTime, processingTime}, originalIndex}
        
        for (int i = 0; i < n; i++) {
            sortedTasks.push_back({{tasks[i][0], tasks[i][1]}, i});
        }
        
        sort(sortedTasks.begin(), sortedTasks.end());
        
        // Min heap: {processingTime, originalIndex}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> availableTasks;
        
        vector<int> result;
        long long currentTime = 0;
        int taskIndex = 0;
        
        while (result.size() < n) {
            // If no tasks available and current time is before next task's enqueue time
            if (availableTasks.empty() && taskIndex < n && currentTime < sortedTasks[taskIndex].first.first) {
                currentTime = sortedTasks[taskIndex].first.first;
            }
            
            // Add all tasks that are available at current time
            while (taskIndex < n && sortedTasks[taskIndex].first.first <= currentTime) {
                availableTasks.push({sortedTasks[taskIndex].first.second, sortedTasks[taskIndex].second});
                taskIndex++;
            }
            
            // Process the task with shortest processing time (and smallest index if tie)
            auto task = availableTasks.top();
            availableTasks.pop();
            result.push_back(task.second);
            currentTime += task.first;
        }
        
        return result;
    }
};

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        import heapq
        
        n = len(tasks)
        # Create list of (enqueueTime, processingTime, originalIndex)
        sorted_tasks = [(tasks[i][0], tasks[i][1], i) for i in range(n)]
        sorted_tasks.sort()
        
        available_tasks = []  # Min heap: (processingTime, originalIndex)
        result = []
        current_time = 0
        task_index = 0
        
        while len(result) < n:
            # If no tasks available and current time is before next task's enqueue time
            if not available_tasks and task_index < n and current_time < sorted_tasks[task_index][0]:
                current_time = sorted_tasks[task_index][0]
            
            # Add all tasks that are available at current time
            while task_index < n and sorted_tasks[task_index][0] <= current_time:
                heapq.heappush(available_tasks, (sorted_tasks[task_index][1], sorted_tasks[task_index][2]))
                task_index += 1
            
            # Process the task with shortest processing time
            processing_time, original_index = heapq.heappop(available_tasks)
            result.append(original_index)
            current_time += processing_time
        
        return result

public class Solution {
    public int[] GetOrder(int[][] tasks) {
        int n = tasks.Length;
        var sortedTasks = new List<(long enqueueTime, int processingTime, int originalIndex)>();
        
        for (int i = 0; i < n; i++) {
            sortedTasks.Add((tasks[i][0], tasks[i][1], i));
        }
        
        sortedTasks.Sort((a, b) => a.enqueueTime.CompareTo(b.enqueueTime));
        
        var availableTasks = new PriorityQueue<(int processingTime, int originalIndex), (int, int)>(
            Comparer<(int, int)>.Create((a, b) => 
                a.Item1 != b.Item1 ? a.Item1.CompareTo(b.Item1) : a.Item2.CompareTo(b.Item2))
        );
        
        var result = new List<int>();
        long currentTime = 0;
        int taskIndex = 0;
        
        while (result.Count < n) {
            if (availableTasks.Count == 0 && taskIndex < n && currentTime < sortedTasks[taskIndex].enqueueTime) {
                currentTime = sortedTasks[taskIndex].enqueueTime;
            }
            
            while (taskIndex < n && sortedTasks[taskIndex].enqueueTime <= currentTime) {
                availableTasks.Enqueue(
                    (sortedTasks[taskIndex].processingTime, sortedTasks[taskIndex].originalIndex),
                    (sortedTasks[taskIndex].processingTime, sortedTasks[taskIndex].originalIndex)
                );
                taskIndex++;
            }
            
            var task = availableTasks.Dequeue();
            result.Add(task.originalIndex);
            currentTime += task.processingTime;
        }
        
        return result.ToArray();
    }
}

var getOrder = function(tasks) {
    const n = tasks.length;
    const indexedTasks = tasks.map((task, i) => [task[0], task[1], i]);
    indexedTasks.sort((a, b) => a[0] - b[0]);
    
    const result = [];
    const heap = [];
    let time = 0;
    let i = 0;
    
    const heapPush = (item) => {
        heap.push(item);
        let idx = heap.length - 1;
        while (idx > 0) {
            const parent = Math.floor((idx - 1) / 2);
            if (heap[parent][0] > heap[idx][0] || 
                (heap[parent][0] === heap[idx][0] && heap[parent][1] > heap[idx][1])) {
                [heap[parent], heap[idx]] = [heap[idx], heap[parent]];
                idx = parent;
            } else {
                break;
            }
        }
    };
    
    const heapPop = () => {
        if (heap.length === 0) return null;
        if (heap.length === 1) return heap.pop();
        
        const result = heap[0];
        heap[0] = heap.pop();
        let idx = 0;
        
        while (true) {
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            let smallest = idx;
            
            if (left < heap.length && 
                (heap[left][0] < heap[smallest][0] || 
                 (heap[left][0] === heap[smallest][0] && heap[left][1] < heap[smallest][1]))) {
                smallest = left;
            }
            
            if (right < heap.length && 
                (heap[right][0] < heap[smallest][0] || 
                 (heap[right][0] === heap[smallest][0] && heap[right][1] < heap[smallest][1]))) {
                smallest = right;
            }
            
            if (smallest === idx) break;
            
            [heap[idx], heap[smallest]] = [heap[smallest], heap[idx]];
            idx = smallest;
        }
        
        return result;
    };
    
    while (result.length < n) {
        while (i < n && indexedTasks[i][0] <= time) {
            heapPush([indexedTasks[i][1], indexedTasks[i][2]]);
            i++;
        }
        
        if (heap.length === 0) {
            time = indexedTasks[i][0];
        } else {
            const [processingTime, taskIndex] = heapPop();
            result.push(taskIndex);
            time += processingTime;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

时间复杂度： O(n log n)，其中 n 是任务数量。主要来自于初始排序和优先队列操作。

空间复杂度： O(n)，用于存储排序后的任务列表、优先队列和结果数组。

相关题目