azl397985856 commented 1 month ago

1834. 单线程 CPU

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/single-threaded-cpu/

前置知识

模拟

堆

题目描述


给你一个二维数组 tasks ，用于表示 n 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。

现有一个单线程 CPU ，同一时间只能执行最多一项任务，该 CPU 将会按照下述方式运行：

如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择执行时间最短的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。一旦某项任务开始执行，CPU 在执行完整个任务前都不会停止。 CPU 可以在完成一项任务后，立即开始执行一项新任务。

返回 CPU 处理任务的顺序。

示例 1：

输入：tasks = [[1,2],[2,4],[3,2],[4,1]] 输出：[0,2,3,1] 解释：事件按下述流程运行：

time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}
同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}
time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}
time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}
同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}
time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}
time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}
time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}
time = 10 ，CPU 完成任务 1 并进入空闲状态

示例 2：

输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] 输出：[4,3,2,0,1] 解释：事件按下述流程运行：

time = 7 ，所有任务同时进入任务队列，可执行任务项 = {0,1,2,3,4}
同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
time = 40 ，CPU 完成任务 1 并进入空闲状态

提示：

tasks.length == n 1 <= n <= 105 1 <= enqueueTimei, processingTimei <= 109

Martina001 commented 1 month ago

优先级队列的排序时间复杂度nlogn；for循环为n，队列操作为logn，故时间复杂度为nlogn 空间复杂度为n

 public int[] getOrder(int[][] tasks) {
        // 这一个模拟题，重点在于如何排序，必须要先按照开始时间进行排序 按此顺序将任务入队列执行，在此基础上，优先级队列要按照持续时间+任务索引排序
        int n = tasks.length;
        // 用mix三维数组保存任务编号
        int mix[][] = new int[n][3];
        for(int i =0;i<n;i++){
            int[] task = tasks[i];
            mix[i] = new int[]{task[0],task[1],i};
        }
        // 先按照任务开始时间升序 后面按照开始时间顺序入队列
        Arrays.sort(mix,(a,b)->a[0]-b[0]);
        // 优先级队列排序：持续时间+任务编号
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
            if(a[1]!=b[1]){
                return a[1]-b[1];
            }
            return a[2]-b[2];
        });

        // i为mix索引，time表示当前执行到了啥时候，index表示结果集res的索引
        int i =0,time =1;
        int res[] = new int[n];
        for(int index =0;index<n;){
            // 满足开始时间小于等于当前时间的，都可以入队列
            while(i<n && mix[i][0]<= time){
                pq.add(mix[i++]);
            }
            // 如果队列为空，那么没有任何任务可以在当前时间之前执行
            if(pq.isEmpty()){
                time = mix[i][0];
            }else{
                int[] cur = pq.poll();
                res[index++] = cur[2];
                // 时间增加当前任务的持续时间
                time+= cur[1];
            }

        }
        return res;
    }

CathyShang commented 1 month ago

优先队列（小顶堆）：当前时刻下，需要处理的任务放入队列

排序：更新时间戳

class Solution {
public:
vector<int> getOrder(vector<vector<int>>& tasks) {
    int n = tasks.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int i, int j){
        return tasks[i][0] < tasks[j][0];
    });
    vector<int> ans;
    long long timesample=1;
    int ptr = 0;
    // 小堆 优先队列
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> q;
    for(int i=0; i<n; ++i){
        if(q.empty()){
            timesample = max(timesample, (long long)tasks[idx[ptr]][0]);
        }
        // 将小于等于时间戳的任务放入
        while(ptr<n && tasks[idx[ptr]][0]<=timesample){
            q.emplace(tasks[idx[ptr]][1], idx[ptr]);// 任务耗时， 索引
            ++ptr;
        }
        auto& process = q.top().first;
        auto& a = q.top().second;
        timesample += process;
        ans.push_back(a);
        q.pop();

    }
    return ans;
}
};

Time O(nlogn)
Space O(n)

xil324 commented 1 month ago

import heapq
class Solution(object):
    def getOrder(self, tasks):
        """
        :type tasks: List[List[int]]
        :rtype: List[int]
        """
        minHeap = []; 
        task_list  = [(task[0],i, task[1]) for i, task in enumerate (tasks)]
        sorted_task_list = sorted(task_list, key = lambda x:x[0])
        result = []
        index = 0
        time = 0
        for _ in tasks:
            if len(minHeap) == 0:
                time = max(time, sorted_task_list[index][0])
            while index < len(tasks) and sorted_task_list[index][0] <= time:
                heapq.heappush(minHeap,(sorted_task_list[index][2], sorted_task_list[index][1]))
                index+=1
            processing_time, task_index = heapq.heappop(minHeap)
            result.append(task_index)
            time += processing_time
        return result

YYYYYTC commented 1 month ago

确保有任务时才从堆中取任务执行，堆为空时时间跳转到下一个任务的时间，不应该在当前时间上增加。 class Solution { func getOrder(_ tasks: [[Int]]) -> [Int] { let indexedTasks = tasks.enumerated().map { ($0.element[0], $0.element[1], $0.offset) } let sortedTasks = indexedTasks.sorted { $0.0 < $1.0 }

var result: [Int] = []
var heap: [(Int, Int)] = []  // (processingTime, index)
var index = 0
var time = 0
let n = tasks.count

while index < n || !heap.isEmpty {
    if heap.isEmpty {
        time = max(time, sortedTasks[index].0)
    }

    while index < n && sortedTasks[index].0 <= time {
        heap.append((sortedTasks[index].1, sortedTasks[index].2))
        heap.sort { $0.0 < $1.0 }  // 保证每次都是最小堆
        index += 1
    }

    let task = heap.removeFirst()  // 弹出堆顶元素
    time += task.0
    result.append(task.1)
}

return result

} } 时间复杂度为O(n log n) 空间复杂度为O(n)

rao-qianlin commented 1 month ago

class Solution { public int[] getOrder(int[][] tasks) { int[][] tt = new int[tasks.length][3]; for (int i = 0; i < tasks.length; ++i) { tt[i][0] = tasks[i][0]; tt[i][1] = tasks[i][1]; tt[i][2] = i; } Arrays.sort(tt, (a, b) -> a[0] - b[0]); PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]);

    int curTime = Integer.MIN_VALUE;
    int p = 0;
    int[] res = new int[tt.length];

    for (int i = 0; i < tt.length; ++i) {
        while (p < tt.length && (tt[p][0] <= curTime || q.isEmpty())) {
            curTime = Math.max(tt[p][0], curTime);
            q.offer(tt[p]);
            p++;
        }
        int[] t = q.poll();
        curTime = curTime + t[1];
        res[i] = t[2];

    }
    return res;
}

}

zhiyuanpeng commented 1 month ago

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        tasks.sort()
        ans = []
        will_pro = []
        time, pro = 0, 0 
        for _ in tasks:
            if not will_pro:
                time = max(time, tasks[pro][0])
            while pro < len(tasks) and tasks[pro][0] <= time:
                heapq.heappush(will_pro, (tasks[pro][2], tasks[pro][1]))
                pro += 1
            en, i = heapq.heappop(will_pro)
            ans.append(i)
            time += en
        return ans

Dtjk commented 1 month ago

class Solution(object): def getOrder(self, tasks): """ :type tasks: List[List[int]] :rtype: List[int] """ from heapq import * if not tasks: return []

    tasks = [(pair[1], index, pair[0]) for index, pair in enumerate(tasks)] 
    tasks.sort(key = lambda x: x[2]) 

    next_task_id = 0 
    cur_time = tasks[0][2]
    min_heap = []
    res = []
    while next_task_id < len(tasks) or min_heap:
        while next_task_id < len(tasks) and tasks[next_task_id][2] <= cur_time:

            heappush(min_heap, tasks[next_task_id])
            next_task_id += 1

        if not min_heap:

            cur_time = tasks[next_task_id][2]
        else
            working_task = heappop(min_heap)
            cur_time += working_task[0]
            res.append(working_task[1])

    return res

leetcode-pp / 91alg-13-daily-check

【Day 33 】2024-05-10 - 1834. 单线程 CPU #34

1834. 单线程 CPU

入选理由

题目地址

前置知识

题目描述