search

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

91 天学算法第五期打卡
55 stars 14 forks source link

【Day 33 】2021-10-12 - 1834. 单线程 CPU #50

Open azl397985856 opened 3 years ago

azl397985856 commented 3 years ago

1834. 单线程 CPU

入选理由

暂无

题目地址

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

前置知识

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

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

返回 CPU 处理任务的顺序。

 

示例 1：

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

示例 2：

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

 

提示：

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

yanglr commented 3 years ago

思路:

题意:

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

很显然, 需要排序和使用队列。

由于后面还是需要排序, 那么我们就使用优先队列来做了。

方法: 排序 + 小顶堆

代码:

实现语言: C++

typedef long long LL; // 防止整型溢出
typedef pair<LL, LL> PLL;  // pair: 处理时间 -> index

class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) 
    {
        for (int i=0; i<tasks.size(); i++) // 加入index, 题目要求在任务池中选任务时需要按下标排序, 下标小的排前面
            tasks[i].push_back(i);

        sort(tasks.begin(), tasks.end());
        priority_queue<PLL, vector<PLL>, greater<>>pq;  /* pair: 处理时间 -> index */

        LL cur = 0;
        vector<int>rets;
        for (int i=0; i<tasks.size(); i++)
        {
            while (cur < tasks[i][0] && !pq.empty())
            {
                rets.push_back(pq.top().second);
                cur+=pq.top().first;
                pq.pop();
            }            

            pq.push({tasks[i][1], tasks[i][2]}); 
            cur = max(cur, (LL)tasks[i][0]);    /* 如果循环结束时, 时间片还没到达, 那就可以将时间直接跳到最近的下一个任务开始的时刻 */
        }
        while (!pq.empty())
        {
            rets.push_back(pq.top().second);
            cur += pq.top().first;
            pq.pop();
        }
        return rets;        
    }
};

复杂度分析:

st2yang commented 3 years ago

思路

代码

复杂度

BpointA commented 3 years ago

思路

用两个堆进行模拟

Python3代码

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        lst=[]
        early=float("inf")
        for i in range(len(tasks)):
            e,r=tasks[i]
            heappush(lst,(e,r,i))
            early=min(early,e)

        cnt=0
        early=lst[0][0]
        wait=[]
        while len(lst)>0:
            e,r,i=heappop(lst)
            if e!=early:
                heappush(lst,(e,r,i))
                break
            heappush(wait,(r,i,e))

        tm=0
        res=[]    
        while cnt<len(tasks):

            if len(wait)==0:
                e,r,i=heappop(lst)
            else:
                r,i,e=heappop(wait)

            tm=max(e,tm)
            end=tm+r
            while len(lst)>0:
                e1,r1,i1=heappop(lst)
                if e1>end:
                    heappush(lst,(e1,r1,i1))
                    break
                heappush(wait,(r1,i1,e1))
            tm=end
            cnt+=1
            res.append(i)
        return res

复杂度

时间复杂度：O(nlogn)，遍历，每次都是堆操作

空间复杂度：O(n) 第一个堆的大小

chenming-cao commented 3 years ago

解题思路

模拟+排序+小顶堆。先将tasks二维数组转化为三维数组，另加入原始index，因为返回结果时要使用index。将三维数组按enqueueTime排序。再建立小顶堆来储存可执行的任务项。遍历三维数组，将任务开始时间满足条件（不大于当前时间）的所有任务放入小顶堆，如果没有符合条件的任务，重置当前时间。然后通过小顶堆选出合适任务，将原始index放入结果数组，更新当前时间。照此循环直至所有任务都排好序放入结果数组。

代码

class Solution {
    public int[] getOrder(int[][] tasks) {
        // convert 2D array to 3D array to store original index information
        int[][] indices = new int[tasks.length][3];
        for (int i = 0; i < tasks.length; i++) indices[i] = new int[]{tasks[i][0], tasks[i][1], i};
        // sort the 3D array according to enqueueTime
        Arrays.sort(indices, new Comparator<int[]>() {
            public int compare(int[] t1, int[] t2) {
                return t1[0] - t2[0];
            }
        });
        // create min-heap to store the tasks ready to execute
        PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] t1, int[] t2) {
                if (t1[0] == t2[0]) return t1[1] - t2[1];
                return t1[0] - t2[0];
            }
        });

        int time = 0;
        int[] res = new int[tasks.length];
        int num = 0;

        for (int i = 0; i < res.length; i++) {
            // no task is ready for current time, reset time
            if (num < indices.length && time < indices[num][0] && heap.isEmpty()) time = indices[num][0]; 
            // put the ready tasks into heap
            while (num < indices.length && time >= indices[num][0]) {
                heap.offer(new int[]{indices[num][1], indices[num][2]});
                num++;
            }
            int[] cur = heap.poll();
            time += cur[0];
            res[i] = cur[1];
        }
        return res;
    }
}

复杂度分析

yachtcoder commented 3 years ago

Heap + simulation. Maintaining timestamp is tricky: should be updated whenever a task finishes; if there's no task in heap, should advance to the next available task and admit all tasks admirable. O(nlgn) and O(n)

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        N = len(tasks)
        tasks = list(zip(tasks, list(range(N))))
        tasks.sort(key = lambda x: x[0][0]) #by starting time
        heap, ts = [], tasks[0][0][0]
        idx, ret = 0, []
        N = len(tasks)
        while heap or idx < N:
            while not heap or (idx < N and tasks[idx][0][0] <= ts):
                task, origidx = tasks[idx]
                heappush(heap, (task[1], origidx, task[0])) #sort by cost
                idx += 1
                ts = max(ts, task[0])
                if idx >= N: break
            t = heappop(heap)
            ts = max(ts, t[2])
            ts += t[0]
            ret.append(t[1])
        return ret
JiangyanLiNEU commented 3 years ago

Two min-heap

one heap is to sort work-item by their available time, time needed, index one heap is to sort work-item which are available for now by time needed, index

leo173701 commented 3 years ago

学到一招： 出现数组的时候，先想想排个序会不会好一点 堆过几天再学吧

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        res = []
        tasks = sorted([(t[0], t[1], i) for i, t in enumerate(tasks)])
        i = 0
        h = []
        time = tasks[0][0]
        while len(res) < len(tasks):
            while (i < len(tasks)) and (tasks[i][0] <= time):
                heapq.heappush(h, (tasks[i][1], tasks[i][2])) # (processing_time, original_index)
                i += 1
            if h:
                t_diff, original_index = heapq.heappop(h)
                time += t_diff
                res.append(original_index)
            elif i < len(tasks):
                time = tasks[i][0]
        return res
zliu1413 commented 3 years ago

import heapq

class Solution: def getOrder(self, tasks: List[List[int]]) -> List[int]: tasks = [[task[0],task[1],idx] for idx, task in enumerate(tasks)] def cmpfunc(a,b): if a[0]>b[0]: return 1 elif a[0]<b[0]: return -1 else: if a[1]>b[1]: return 1 elif a[1]<b[1]: return -1 else: return 0

    tasks=sorted(tasks,key=functools.cmp_to_key(cmpfunc))
    #tasks.sort()

    waits = []
    heapq.heapify(waits)
    time = 0
    pos = 0
    res = []
    n = len(tasks)
    for _ in range(n):
        if not waits:
            time = max(time,tasks[pos][0])
        while pos<n and tasks[pos][0]<=time:
            heapq.heappush(waits,[tasks[pos][1],tasks[pos][2]])
            pos += 1
        dur,idx = heapq.heappop(waits)
        time += dur
        res.append(idx)
    return res

time: O(nlogn) space: O(n)

AgathaWang commented 3 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        # simulation
        # add index
        tasks = [[y[0],j,y[1]] for j,y in enumerate(tasks)]
        tasks.sort() # sort based on the first element
        pos = 0
        time = 0
        queue = []  # available tasks
        ans = []
        for _ in tasks:
            # CPU处理完了空闲，还没到下一个任务时间，快进time
            if not queue:
                time = max(time,tasks[pos][0])
            # 这个time时应该进入queue的任务
            while pos < len(tasks) and tasks[pos][0] <= time:
                # 注意这里入堆顺序，因为堆按process time排序，所以tasks[pos][2]放前面
                heapq.heappush(queue,(tasks[pos][2],tasks[pos][1]))   
                pos += 1
            # print(queue)
            pt,idx = heapq.heappop(queue)
            time += pt
            ans.append(idx)
        return ans
# time complexity: O(NlogN)
thinkfurther commented 3 years ago

思路

首先按照开始时刻进行排序，然后按照时间插入到最小堆里，接着执行

代码

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        import heapq
        tasks_list = [(i, task[0] ,task[1]) for i, task in enumerate(tasks)]
        tasks_list = sorted(tasks_list, key = lambda x: (x[1],x[0]))
        backlog = []
        time = 0
        ans = []
        pos = 0
        process
        for _ in tasks_list:
            if not backlog:
                time = max(time, tasks[pos][1])
            while pos < len(tasks) and tasks_list[pos][1]< time:
                heapq.heappush(backlog ,(tasks_list[pos][2], tasks_list[pos][0]))
                pos += 1            
            delta_time, index = heapq.heappop(backlog)
            time += delta_time
            ans.append(index)            
        return ans

复杂度

时间复杂度 ：O(NlogN)

空间复杂度：O(N)

wangzehan123 commented 3 years ago 

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        int[][] arr = new int[n][];
        for(int i = 0;i<n;i++) arr[i] = new int[]{tasks[i][0],tasks[i][1],i};
        Arrays.sort(arr,(x,y)->(x[0]-y[0]));
        int idx = 0;
        long cur = arr[0][0];
        int[] res = new int[n];
        PriorityQueue<int[]> que = new PriorityQueue<>((x,y)->(x[1]-y[1]==0?x[2]-y[2]:x[1]-y[1]));
        for(int i = 0;i<n;i++){
            if(que.isEmpty()&&idx<n&&cur<arr[idx][0]) cur = arr[idx][0];
            while(idx<n&&arr[idx][0]<=cur) que.offer(arr[idx++]);
            int[] t = que.poll();
            res[i] = t[2];
            cur+=t[1];
        }
        return res;
    }
}

复杂度分析

令 n 为数组长度。

xj-yan commented 3 years ago 
class Solution {
    public int[] getOrder(int[][] tasks) {
        int[][] sortedTask = new int[tasks.length][3];
        for (int i = 0; i < tasks.length; i++){
            sortedTask[i] = new int[]{tasks[i][0], tasks[i][1], i};
        }
        Arrays.sort(sortedTask, (a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> taskQueue = new PriorityQueue<>(new Comparator<int[]>(){
                        public int compare(int[] a, int[] b){
                if (a[0] == b[0]) return a[1] - b[1];
                return a[0] - b[0];
            }
        });

        int[] order = new int[tasks.length];
        int time = sortedTask[0][0], index = 0, orderIndex = 0;
        while (orderIndex < tasks.length){
            while (index < sortedTask.length && time >= sortedTask[index][0]){
                taskQueue.offer(new int[]{sortedTask[index][1], sortedTask[index][2]});
                index++;
            }
            if (!taskQueue.isEmpty()){
                int[] curt = taskQueue.poll();
                order[orderIndex++] = curt[1];
                time += curt[0];
            }else if (index < sortedTask.length){
                time = sortedTask[index][0];
            }
        }

        return order;
    }
}

Time Complexity: O(NlogN), Space Complexity: O(n)

zol013 commented 3 years ago

先对tasks进行排序来保证tasks的时间是有序的，用time来模拟时间进程， 创建一个极小堆来保存enqueue time 小于 time的任务， 用pos 指针将tasks里的所有enqueue time 小于 time的任务保存到heap里, 每次heappop出process time最少的任务 

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [[tasks[i][0], tasks[i][1], i] for i in range(len(tasks))]
        tasks.sort()
        available_tasks = []
        ans = []
        time =  0
        pos = 0
        for _ in tasks:
            if not available_tasks:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heappush(available_tasks, [tasks[pos][1], tasks[pos][2]])
                pos += 1
            process_time, task_about_to_do = heappop(available_tasks)
            time += process_time
            ans.append(task_about_to_do)
        return ans

Time Complexity: O(nlogn) Space Complexity: O(n)

pophy commented 3 years ago

思路

Java Code

class Solution {
    public int[] getOrder(int[][] tasks) {
        PriorityQueue<Task> queue = new PriorityQueue<>((a, b) -> {
            if (a.processingTime == b.processingTime) {
                return a.id - b.id;
            }
            return a.processingTime - b.processingTime;
        });

        List<Task> taskList = new ArrayList<>();
        for (int i = 0; i < tasks.length; i++) {
            taskList.add(new Task(i, tasks[i][0], tasks[i][1]));
        }
        Collections.sort(taskList, (a, b) -> a.startTime == b.startTime ? a.processingTime - b.processingTime : a.startTime - b.startTime);
        taskList.stream().forEach(t -> System.out.println(t.id + " s: " + t.startTime + " p: " + t.processingTime));
        int currentTime = 0;
        List<Integer> processedTask = new ArrayList<>();
        for (int i = 0, index = 0; index < taskList.size();) {
            while (i < taskList.size() && taskList.get(i).startTime <= currentTime) {
                queue.add(taskList.get(i));
                i++;
            }
            if (queue.isEmpty()) {
                currentTime = taskList.get(i).startTime;
            } else {
                Task task = queue.poll();
                processedTask.add(task.id);
                currentTime += task.processingTime;
                index++;
            }
        }

        int[] res = new int[processedTask.size()];
        for (int i = 0; i < processedTask.size(); i++) {
            res[i] = processedTask.get(i);
        }
        return res;
    }

    public static class Task {
        public int id;
        public int startTime;
        public int processingTime;

        public Task(int id, int startTime, int processingTime) {
            this.id = id;
            this.startTime = startTime;
            this.processingTime = processingTime;
        }
    }  
}

时间&空间

cicihou commented 3 years ago 

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        '''
        enqueueTime 表示在这个时间及之后，这个任务才可以加载进队列
        processingTime 表示这个任务需要的处理时间

        我们每次处理的是，当前排队的任务队列中耗时最短的那个任务

        若「消息队列mq」中无任务，将时间直接拨到当前对应下个任务的开始时间
        如果当前的时间 >= 下个对应任务的开始时间，则将对应的任务加进 mq，表示任务已经开始等待
            mq 中的任务格式为 (task_index, task_processing_time)
        取出当前 min_heap 中最小的任务（由于 processing_time 放在前面，也就是所有在 mq 中 processing_time 最小的任务）
        当前时间向后（产生了耗时），将 index 加入结果集
        '''
        tasks = [(*task, i) for i, task in enumerate(tasks)]
        tasks.sort()
        mq = []
        time = 0
        res = []
        i = 0
        for _ in tasks:
            if not mq:
                time = max(time, tasks[i][0])
            while i < len(tasks) and tasks[i][0] <= time:
                heapq.heappush(mq, (tasks[i][1], tasks[i][2]))
                i += 1
            process_time, index = heapq.heappop(mq)
            time += process_time
            res.append(index)
        return res
zhangzz2015 commented 3 years ago

思路

关键点

代码

C++ Code:


struct cmp
{
    bool operator()(vector<int>& node1, vector<int>& node2)
    {
            if(node1[1]==node2[1])
            {
                return node1[2]>node2[2];
            }
            else
                return node1[1]>node2[1]; 
    }
};
class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {

        ///   
        priority_queue<vector<int>, vector<vector<int>>, cmp> pq; 

        for(int i=0; i< tasks.size(); i++)
        {
            tasks[i].push_back(i);
        }

        sort(tasks.begin(),tasks.end()); 
        long long currentTime = -1;         
        vector<int> ret; 
        int start =0;
        while(pq.size()||start<tasks.size())
        {
            // put job into pq. 
            while(start<tasks.size() && tasks[start][0]<=currentTime)
            {
               pq.push(tasks[start]);                    
                start++;
            }

            if(pq.size()) // choose one job. 
            {
            vector<int> topNode = pq.top();  
            currentTime = currentTime+ topNode[1];  
            ret.push_back(topNode[2]); 
            pq.pop();                
            }
            else
            {
                currentTime = tasks[start][0]; 
            }
        }
        return ret; 
    }
};
james20141606 commented 3 years ago

Day 33: 1834. Single-Threaded CPU (string, array, heap, simulation)

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        #we add task index to the tasks. Now it is start time, task index, duration
        tasks.sort()
        #sort by start time
        backlog = []
        ans = []
        time = 0
        pos = 0
        #we use pos to iterate through all the tasks
        for _ in tasks:
            if not backlog:
                #if no tasks in the backlog, fast forward to the next task's start time using pos
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                #push all the tasks starting before current time to the backlog, using heap
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1])) #only push duration and task index
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans
Daniel-Zheng commented 3 years ago

思路

排序 + 优先队列。

代码(C++)

class Solution {
private:
    using PII = pair<int, int>;
    using LL = long long;

public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n = tasks.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            return tasks[i][0] < tasks[j][0];
        });

        vector<int> ans;
        priority_queue<PII, vector<PII>, greater<PII>> q;
        LL timestamp = 0;
        int ptr = 0;

        for (int i = 0; i < n; ++i) {
            if (q.empty()) timestamp = max(timestamp, (LL)tasks[indices[ptr]][0]);
            while (ptr < n && tasks[indices[ptr]][0] <= timestamp) q.emplace(tasks[indices[ptr]][1], indices[ptr++]);
            auto&& [process, index] = q.top();
            timestamp += process;
            ans.push_back(index);
            q.pop();
        }
        return ans;
    }
};

复杂度分析

laofuWF commented 3 years ago 
# sort by start time > process time > index
# push all tasks that has start time <= curr_time to a heap (process time, index)
# process tasks in the queue if there are some tasks in there
# otherwise move to curr time to next start time

# time: O(NlogN) for sorting and push/pop operations of heap
# space: O(N)

import heapq

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        # sort by start time so that CPU picks ones with earliest start time first
        sorted_tasks = sorted([(t[0], t[1], i) for i, t in enumerate(tasks)])

        time = sorted_tasks[0][0]
        queue = []
        i = 0
        res = []

        while len(res) < len(tasks):
            while i < len(tasks) and time >= sorted_tasks[i][0]:
                # (process_time, original_index)
                heapq.heappush(queue, (sorted_tasks[i][1], sorted_tasks[i][2]))
                i += 1

            if queue:
                curr_task = heapq.heappop(queue)
                time += curr_task[0]
                res.append(curr_task[1])
            else:
                # idle, move to next coming up task(s)
                time = sorted_tasks[i][0]

        return res
heyqz commented 3 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        for i, t in enumerate(tasks):
            t.append(i)
        tasks.sort(key=lambda x: x[0])

        res, minHeap = [], []
        i, time = 0, tasks[0][0] 

        while minHeap or i < len(tasks):
            while i < len(tasks) and time >= tasks[i][0]: 
                heapq.heappush(minHeap, [tasks[i][1], tasks[i][2]]) 
                i += 1

            if not minHeap: 
                time = tasks[i][0]
            else:
                procTime, index = heappop(minHeap)
                time += procTime
                res.append(index)

        return res

Time: O(nlogn) Space: O(n)

JLin-data commented 3 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        tasks = [(starts, takes, idx) for idx, (starts, takes) in enumerate(tasks)]
        tasks.sort(key = lambda x: x[0])
        tasks.append([math.inf, math.inf, math.inf])
        ans, hp = [], []
        time = tasks[0][0]
        i = 0
        while i <= n:
            starts, takes, idx = tasks[i]
            while i < n and starts <= time:
                heapq.heappush(hp, (takes, idx))
                i += 1
                starts, takes, idx = tasks[i]
            if not hp:
                heapq.heappush(hp, (takes, idx))
                time = starts
                i += 1
            takes, idx = heapq.heappop(hp)
            ans.append(idx)
            time += takes
        ans.pop()
        return ans
littlemoon-zh commented 3 years ago

day 33

1834. Single-Threaded CPU

from heapq import *

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [tasks[i] + [i] for i in range(len(tasks))]
        tasks.sort()
        time = tasks[0][0]
        res = []
        q = []
        i = 0
        while len(res) != len(tasks):
            while i < len(tasks) and (tasks[i][0] <= time): 
                heappush(q, [tasks[i][1], tasks[i][2]])
                i += 1
            if q:
                process, index = heappop(q)
                res.append(index)
                time += process
            elif i < len(tasks):
                time = tasks[i][0]

        return res

Time: nlogn Space: O(n)

nonevsnull commented 3 years ago

思路

AC

代码

class Solution {
    public int[] getOrder(int[][] tasks) {
        int[] res = new int[tasks.length];
        int[][] copy = new int[tasks.length][tasks[0].length+1];
        for(int i = 0;i < tasks.length;i++){
            copy[i][0] = tasks[i][0];
            copy[i][1] = tasks[i][1];
            copy[i][2] = i;
        }
        Arrays.sort(copy, Comparator.<int[]>comparingInt(o -> o[0]));
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.<int[]>comparingInt(o -> o[1]).thenComparingInt(o -> o[2]));
        int time = 0;
        int taskIndex = 0;
        int resIndex = 0;

        while(resIndex < res.length){
            while(taskIndex < tasks.length && copy[taskIndex][0] <= time){
                heap.add(new int[]{copy[taskIndex][0], copy[taskIndex][1], copy[taskIndex][2]});
                taskIndex++;
            }
            if(heap.isEmpty()){
                time = copy[taskIndex][0];
                continue;
            }

            int[] top = heap.poll();
            res[resIndex++] = top[2];
            time += top[1];      
        }

        return res;
    }
}

复杂度

time: O(NlogN)，因为sort了。 space: O(N)，有辅助array和heap。

yan0327 commented 3 years ago

思路： 太久没写堆了，问题好大。感觉是很简单的模拟，但是实际写起来不熟悉。 前面是正常的堆引入，只是以一个结构体作为堆的基本参数，如strcut{t,i} t代表持续时间，i代表索引 因此Less里面 先找t小的，如果t相等则找i小的 由于答案需要返回一个索引，所以首先遍历数组时应该添加第三个索引参数i 再来一个基于起始时间的升序排序。 初始化堆， for循环：1.若堆长度不为0，则出堆一个结构体，把这个结构体的索引插入输出数组，当前时间加上持续时间 2.若堆长度为0且低于开始时间，则当前时间为开始时间 3一个for循环把所有低于当前时间的任务，的持续时间和索引丢进堆里

type pair struct{t,i int}
type Iheap []pair
func (h Iheap) Len() int{
    return len(h)
}
func (h Iheap) Less(i,j int) bool{
    a,b := h[i],h[j]
    return a.t < b.t || a.t == b.t && a.i < b.i
}
func (h Iheap) Swap(i, j int){h[i],h[j] = h[j],h[i]}
func (h *Iheap)Push(v interface{}) {*h = append(*h,v.(pair))}
func (h *Iheap)Pop() interface{}{
    x := *h
    out := x[len(x)-1]
    *h = x[:len(x)-1]
    return out
}

func getOrder(tasks [][]int) []int {
    out := []int{}
    for i := range tasks{
        tasks[i] = append(tasks[i],i)
    }
    sort.Slice(tasks, func(i,j int) bool{
        return tasks[i][0] < tasks[j][0]
    })
    var h Iheap
    heap.Init(&h)
    for i,cur,n := 0,0,len(tasks); i < n;{
        if h.Len() > 0{
            p := heap.Pop(&h).(pair)
            out = append(out,p.i)
            cur += p.t
        }
        if h.Len() == 0 && cur < tasks[i][0]{
            cur = tasks[i][0]
        }
        for ;i<n && tasks[i][0] <= cur;i++{
            heap.Push(&h,pair{tasks[i][1],tasks[i][2]})
        }
    }
    for h.Len() > 0 {
        out = append(out,heap.Pop(&h).(pair).i)
    }
    return out
}

时间复杂度:O(NLogN) 空间复杂度:O(N)

GZ712D commented 3 years ago

思路

先整理队列，然后按规则择优有序进出

代码：

class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
tasks = [[tasks[i][0], tasks[i][1], i] for i in range(len(tasks))]
tasks.sort()
available_tasks = []
ans = []
time = 0
pos = 0

复杂度

时间复杂度: O(nlogn) 空间复杂度: O(n)

MoncozGC commented 3 years ago

type pair struct{t,i int} type Iheap []pair func (h Iheap) Len() int{ return len(h) } func (h Iheap) Less(i,j int) bool{ a,b := h[i],h[j] return a.t < b.t || a.t == b.t && a.i < b.i } func (h Iheap) Swap(i, j int){h[i],h[j] = h[j],h[i]} func (h Iheap)Push(v interface{}) {h = append(h,v.(pair))} func (h Iheap)Pop() interface{}{ x := h out := x[len(x)-1] h = x[:len(x)-1] return out }

func getOrder(tasks [][]int) []int { out := []int{} for i := range tasks{ tasks[i] = append(tasks[i],i) } sort.Slice(tasks, func(i,j int) bool{ return tasks[i][0] < tasks[j][0] }) var h Iheap heap.Init(&h) for i,cur,n := 0,0,len(tasks); i < n;{ if h.Len() > 0{ p := heap.Pop(&h).(pair) out = append(out,p.i) cur += p.t } if h.Len() == 0 && cur < tasks[i][0]{ cur = tasks[i][0] } for ;i<n && tasks[i][0] <= cur;i++{ heap.Push(&h,pair{tasks[i][1],tasks[i][2]}) } } for h.Len() > 0 { out = append(out,heap.Pop(&h).(pair).i) } return out }

BlueRui commented 3 years ago

Problem 1834. Single-Threaded CPU

Algorithm

  1. First sort all tasks by the start time.
  2. Then for the current time, add all tasks that can be started to a priority queue which sorts by task processing time.
  3. Pop a task out of the priority queue and update current time.
  4. Repeat step 2 and 3. If current time is smaller then the start time of any task, set it to the smallest start time.

Complexity

Code

Language: Java

public int[] getOrder(int[][] tasks) {
    int n = tasks.length;
    int[] result = new int[n];
    int[][] tasksWithInd = new int[n][3];
    for (int i = 0; i < n; i++) {
        tasksWithInd[i][0] = tasks[i][0];
        tasksWithInd[i][1] = tasks[i][1];
        tasksWithInd[i][2] = i;
    }
    Arrays.sort(tasksWithInd, (a, b) -> a[0] - b[0]);
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]);
    int curTime = 0;
    int resultInd = 0;
    int taskInd = 0;
    while (resultInd < n) {
        while (taskInd < n && tasksWithInd[taskInd][0] <= curTime) {
            pq.offer(tasksWithInd[taskInd++]);
        }
        if (pq.isEmpty()) {
            curTime = tasksWithInd[taskInd][0];
            continue;
        }
        int[] curTask = pq.poll();
        result[resultInd++] =  curTask[2];
        curTime += curTask[1];
    }
    return result;
}
yingliucreates commented 3 years ago

link:

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

代码 Javascript

const priorAssign = 10 ** 5;
const getOrder = (tasks) => {
  tasks = tasks.map((t, i) => [...t, i]);
  tasks.sort((x, y) => y[0] - x[0]);

  let pq = new MinPriorityQueue({
    priority: ([et, pt, idx]) => pt * priorAssign + idx,
  });
  let curTask = tasks[tasks.length - 1][0];
  let res = [];
  while (tasks.length || pq.size()) {
    while (tasks.length && curTask >= tasks[tasks.length - 1][0]) {
      pq.enqueue(tasks.pop());
    }
    if (pq.size()) {
      let [et, pt, idx] = pq.dequeue().element;
      curTask += pt;
      res.push(idx);
    } else if (tasks.length) {
      curTask = tasks[tasks.length - 1][0];
    }
  }
  return res;
};
ZacheryCao commented 3 years ago

Solution

sort + heap.

Code(Python)

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        res = []
        tasks = sorted([(t[0], t[1], i) for i, t in enumerate(tasks)])
        i = 0
        h = []
        time = tasks[0][0]
        while len(res) < len(tasks):
            while (i < len(tasks)) and (tasks[i][0] <= time):
                heapq.heappush(h, (tasks[i][1], tasks[i][2])) # (processing_time, original_index)
                i += 1
            if h:
                t_diff, original_index = heapq.heappop(h)
                time += t_diff
                res.append(original_index)
            elif i < len(tasks):
                time = tasks[i][0]
        return res

complexity:

Time: O(NlogN). Heappush is O(logN). Sort is O(NlogN) Space:O(N)

Kashinggo commented 3 years ago

思路

遇到优先队列就死机，mark 一下。

代码

class Solution {
    public int[] getOrder(int[][] ts) {
        int n = ts.length;

        int[][] nts = new int[n][3];
        for (int i = 0; i < n; i++) nts[i] = new int[]{ts[i][0], ts[i][1], i};
        // 根据任务入队时间进行排序
        Arrays.sort(nts, (a,b)->a[0]-b[0]);
        // 根据题意，先按照「持续时间」排序，再根据「任务编号」排序
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        int[] ans = new int[n];
        for (int time = 1, j = 0, idx = 0; idx < n; ) {
            // 如果当前任务可以添加到「队列」中（满足入队时间）则进行入队
            while (j < n && nts[j][0] <= time) q.add(nts[j++]);
            if (q.isEmpty()) {
                // 如果当前「队列」没有任务，直接跳到下个任务的入队时间
                time = nts[j][0];
            } else {    
                int[] cur = q.poll();
                ans[idx++] = cur[2];
                time += cur[1];
            }
        }
        return ans;
    }
}

复杂度

wenlong201807 commented 3 years ago

代码块


class Heap {
  constructor(compare) {
    this.A = [];
    this.compare = compare;
  }
  size() {
    return this.A.length;
  }
  left(i) {
    return 2 * i + 1;
  }
  right(i) {
    return 2 * i + 2;
  }
  parent(i) {
    return i > 0 ? (i - 1) >>> 1 : -1;
  }
  isEmpty() {
    return this.size() === 0;
  }
  peek() {
    return this.A[0];
  }
  heapifyDown(i) {
    let p = i;
    const l = this.left(i),
      r = this.right(i),
      size = this.size();
    if (l < size && this.compare(l, p)) p = l;
    if (r < size && this.compare(r, p)) p = r;
    if (p !== i) {
      this.exchange(i, p);
      this.heapifyDown(p);
    }
  }
  heapifyUp(i) {
    const p = this.parent(i);
    if (p >= 0 && this.compare(i, p)) {
      this.exchange(i, p);
      this.heapifyUp(p);
    }
  }
  exchange(x, y) {
    const temp = this.A[x];
    this.A[x] = this.A[y];
    this.A[y] = temp;
  }
  compare() {
    throw new Error('Must be implement!');
  }
}

class PriorityQueue extends Heap {
  constructor(compare) {
    super(compare);
  }
  enqueue(node) {
    this.A.push(node);
    this.heapifyUp(this.size() - 1);
  }
  dequeue() {
    const first = this.A[0];
    const last = this.A.pop();
    if (first !== last) {
      this.A[0] = last;
      this.heapifyDown(0);
    }
    return first;
  }
}

/**
 * @param {number[][]} tasks
 * @return {number[]}
 */
var getOrder = function (tasks) {
  // 为每个 task 添加一个索引属性并排序
  tasks.forEach((v, i) => v.push(i));
  tasks.sort((a, b) => b[0] - a[0]);

  // 初始化小根堆/优先队列
  const heap = new PriorityQueue(function (x, y) {
    // 第一优先级为执行时间，第二优先级为任务索引
    return this.A[x][1] !== this.A[y][1]
      ? this.A[x][1] < this.A[y][1]
      : this.A[x][2] < this.A[y][2];
  });
  const ans = [];
  // CPU 时间：初始化为首个任务的开始时间
  let time = tasks[tasks.length - 1][0];

  // 保证执行完所有任务
  while (heap.size() || tasks.length) {
    // 取出任务队列中优先级最高的任务
    if (!heap.isEmpty()) {
      const task = heap.dequeue();
      ans.push(task[2]); // 记录结果
      time += task[1]; // 任务执行完毕，递增 CPU 时间
    }

    // 添加任务到任务队列
    addTask(heap, tasks, time);

    // 边界：任务队列为空（剩余任务的入队时间跨度太大，导致上一步未能添加任务）
    if (heap.isEmpty() && tasks.length) {
      // 将 CPU 时间快进到下一个任务，并添加任务到任务队列
      time = tasks[tasks.length - 1][0];
      addTask(heap, tasks, time);
    }
  }

  return ans;
};

function addTask(heap, tasks, time) {
  // 将 tasks 中入队时间不快于当前 CPU 时间的任务入队
  while (tasks.length && tasks[tasks.length - 1][0] <= time) {
    heap.enqueue(tasks.pop());
  }
}

时间复杂度和空间复杂度

shixinlovey1314 commented 3 years ago

Title:1834. Single-Threaded CPU

Question Reference LeetCode

Solution

1 sort the array based on the enqueue time. 2 based on the current time, find the available tasks. 3 sort the available tasks based on processing time. 4.pick the shorted tasks from the available tasks, update the current time, if there's no available task base on current time, fast forward to the next time a task is avaible.

Code

class Solution {
public:
    typedef struct Task{
        int eTime;
        int pTime;
        int index;
        Task(int e, int p, int i): eTime(e), pTime(p), index(i){}
    }Task;
    struct orgComp {
        bool operator()(Task& a, Task& b) {
            if (a.eTime > b.eTime)
                return true;
            else
                return false;
        }
    };
    struct aviComp {
       bool operator()(Task& a, Task& b) {
            if (a.pTime > b.pTime)
                return true;
            else if (a.pTime < b.pTime)
                return false;
            else
                return a.index > b.index;
        } 
    };

    vector<int> getOrder(vector<vector<int>>& tasks) {
        vector<int> result;
        priority_queue<Task, vector<Task>, orgComp> orgQueue;
        priority_queue<Task, vector<Task>, aviComp> aviQueue;

        for (int i = 0; i < tasks.size(); i++) {
            Task task(tasks[i][0], tasks[i][1], i);
            orgQueue.push(task);
        }

        long long curTime = orgQueue.top().eTime;

        while (!orgQueue.empty() || !aviQueue.empty()) {
            if (aviQueue.empty() && orgQueue.top().eTime > curTime)
                curTime = orgQueue.top().eTime;

            while (!orgQueue.empty() && orgQueue.top().eTime <= curTime) {
                aviQueue.push(orgQueue.top());
                orgQueue.pop();
            }

            if (!aviQueue.empty()) {
                result.push_back(aviQueue.top().index);
                curTime += aviQueue.top().pTime;
                aviQueue.pop();
            }
        }

        return result;
    }
};

Complexity

Time Complexity and Explanation

O(nlogn) use to build the heap.

Space Complexity and Explanation

O(n)

falconruo commented 3 years ago

思路:

方法一、

  1. 定义一个数据类型Task = vector， 包含三个元素{enqueueTime, processingTime, i}
  2. 使用小顶堆(优先队列priority_queue)首先按照enqueueTime的大小入堆, 自定义比较函数cmp_enqueue, 按照enqueueTime (a[0] > b[0])
  3. 循环
    • 从堆enqueueT中取堆顶元素(enqueueTime最小值)，计算最新的时间timestamp
    • 从堆enqueueT中取出所有开始时间(enqueueTime）小于大于当前时间timestamp的任务,放入新的小顶堆processT中，同时从堆enqueueT中出堆，堆processT中包含当前所有ready可以执行的任务 新的小顶堆processT按照processTime的大小排序,自定义比较函数cmp_process，按照processTime （a[1] > b[1]）, 如果processTime相等，按照index(a[2] > b[2])排序
    • 取堆processT的堆顶元素(符合要求的Task)，放入返回数组res中（processT.top()[2]）
    • 更新当前时间timestamp += 堆顶元素的processingTime

复杂度分析:

  1. 时间复杂度: O(nlogn), 其中 n是task数
  2. 空间复杂度: O(n)

代码(C++):

方法一、
class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n = tasks.size();

        if (n <= 1) return {n - 1};

        vector<int> res;

        auto cmp_enqueueT = [](const Task &a, const Task &b) {
            return a[1] < b[1];
        };

        auto cmp_processT = [](const Task &a, const Task &b) {
            return a[1] < b[1] || a[1] == b[1] & a[2] < b[2];
        };

        priority_queue<Task, vector<Task>, decltype(cmp_enqueueT)> equeue_task(cmp_enqueueT);
        priority_queue<Task, vector<Task>, decltype(cmp_processT)> process_task(cmp_processT);

        for (int i = 0; i < n; ++i) {
            equeue_task.push({tasks[i][0], tasks[i][1], i});
        }

        long timestamp = 0;
        while (res.size() < n) {
            if (process_task.empty())
                timestamp = timestamp >= equeue_task.top()[0] ? timestamp : equeue_task.top()[0];

            while (!equeue_task.empty() && equeue_task.top()[0] <= timestamp) {
                process_task.push(equeue_task.top());
                equeue_task.pop();
            } // add all ready tasks into heap process_task which can be started once CPU is ready

            // add the smallest processing time task into return array
            res.push_back(process_task.top()[2]);
            // update timestamp to ensure new ready tasks can be put into heap process_task
            timestamp += process_task.top()[1];
            process_task.pop();
        }

        return res;
    }
private:
    // {enqueueTime, processingTime, i}
    using Task = vector<int>;
};
chakochako commented 3 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [[idx, t, d] for idx, (t, d) in enumerate(tasks)]
        tasks.sort(key=lambda x: (x[1])) #按照时间升序排序
        cur_t = tasks[0][1] # 以所有task最小时间作为当前时间
        res = []
        heap = []
        n = len(tasks)
        idx = 0 #当前处理的task位置
        while len(res) != n: # 当未处理完所有task时
            while idx < n and tasks[idx][1] <= cur_t: #将时间小于等于当前时间的task入堆
                t = tasks[idx]
                heapq.heappush(heap, [t[2], t[0], t[1]])  # d, idx, t
                idx += 1
            if not heap: #都比当前时间大，将余下task最小的时间作为当前时间
                cur_t = tasks[idx][1]
                continue
            cur_task = heapq.heappop(heap)
            res.append(cur_task[1])
            cur_t = cur_t + cur_task[0] 
        return res
RocJeMaintiendrai commented 3 years ago

题目

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

思路

新建一个三元数组[下标，入队时间，处理时间]并按照入队时间进行排序，并新建一个pq，pq是当前在等待处理的task，所以首先按照处理时间进行排序，然后按照入队时间进行排序。用cur表示当前时间，从0开始，idx为处理到的tasks，要将time开始前所有的task都加入到queue里来准备被处理。

代码

class Solution {
    public int[] getOrder(int[][] tasks) {
        final int n = tasks.length;
        //新建一个三元数组[下标，入队时间，处理时间]
        int[][] taskWithId = new int[n][3];
        for(int i = 0; i < n; i++) {
            taskWithId[i] = new int[]{i, tasks[i][0], tasks[i][1]};
        }
        //按照入队时间进行排序
        Arrays.sort(taskWithId, (a, b) -> (a[1] - b[1]));
        //处理时间不同按照处理时间从小到大，否则按照入队时间
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if(a[2] != b[2]) {
                return a[2] - b[2];
            }
            return a[0] - b[0];
        });
        int idx = 0;
        int i = 0;
        int cur = 0;
        int[] res = new int[n];
        while(!pq.isEmpty() || idx < n) {
            //如果没有要处理的task，且还没有进入到下一个task的时间，就快进过去
            if(pq.isEmpty() && idx < n && cur < taskWithId[idx][1]) {
                cur = taskWithId[idx][1];
            }
            //处理一个task或快进到后需要入队的task
            while(idx < n && taskWithId[idx][1] <= cur) {
                pq.offer(taskWithId[idx++]);
            }
            int[] task = pq.poll();
            res[i++] = task[0];
            cur += task[2];
        }
        return res;
    }
}

复杂度分析

时间复杂度

O(nlogn)

空间复杂度

O(n)

shamworld commented 3 years ago

思路

抄下

代码

var getOrder = function(tasks) {
    const res=[];
    const queue = new MinPriorityQueue();
    tasks = tasks.map((task, index) => ({
        index,
        start: task[0],
        time: task[1]
    }))
    // 下边用shift()形式 会超时，shift耗时比pop要长
    tasks.sort((a, b) => b.start - a.start);
    let time = 0;
    while(tasks.length || !queue.isEmpty()){
        if (queue.isEmpty() && tasks[tasks.length - 1].start > time) {
            time = tasks[tasks.length - 1].start
        }
        while (tasks.length > 0 && tasks[tasks.length - 1].start <= time) {
            const task = tasks.pop();
            queue.enqueue(task, task.time * 100000 + task.index)
        }
        const { element } = queue.dequeue()
        time += element.time;
        res.push(element.index);
    }
    return res;
};
biancaone commented 3 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        if not tasks:
            return []

        result = []
        tasks = sorted([(t[0], t[1], i) for i, t in enumerate(tasks)], key=lambda x: (x[0], x[1], x[2]))

        i = 0
        heap = []
        time = tasks[0][0]

        while len(result) < len(tasks):
            while (i < len(tasks)) and (tasks[i][0] <= time):
                heapq.heappush(heap, (tasks[i][1], tasks[i][2])) # (processing_time, original_index)
                i += 1
            if heap:
                t_diff, original_index = heapq.heappop(heap)
                time += t_diff
                result.append(original_index)
            elif i < len(tasks):
                time = tasks[i][0]

        return result
skinnyh commented 3 years ago

Note

Solution

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(t[0], t[1], i) for i, t in enumerate(tasks)]
        tasks.sort() # sort by enqueue time
        res = []
        idx = time = 0
        q = []
        while len(res) < len(tasks):
            if not q:
                time = max(time, tasks[idx][0])
            while idx < len(tasks) and tasks[idx][0] <= time:
                heapq.heappush(q, (tasks[idx][1], tasks[idx][2])) # add processing time and index to heap
                idx += 1
            t = heapq.heappop(q)
            res.append(t[1])
            time += t[0]
        return res

Time complexity: O(NlogN)

Space complexity: O(N)

akxuan commented 3 years ago

这题非常好, 需要在刷几遍

大概思路就是先用start time sort, 然后弄个priority queue 去process 最小的那个 时间复杂度 O(NlogN) 空间复杂度 O(N)

import heapq

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        for i,c in enumerate(tasks):
            c.append(i)
        tasks.sort(reverse=True)
        available=[]
        res=[]
        currTime=tasks[-1][0]
        while tasks or available:
            if tasks and tasks[-1][0]>currTime and not available:
                currTime=tasks[-1][0]
            if tasks and tasks[-1][0]<=currTime:
                while tasks and tasks[-1][0]<=currTime:
                    heapq.heappush(available,(tasks[-1][1],tasks[-1][2]))
                    tasks.pop()
            if available:
                time,index=heapq.heappop(available)
                currTime+=time
                res.append(index)
            # print(currTime)
        return res
xieyj17 commented 3 years ago 
from collections import deque
import heapq
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(start, task_length, index) for index, (start, task_length) in enumerate(tasks)]
        tasks = sorted(tasks)
        tasks = deque(tasks)
        res = []
        curr_time = 0
        heap = []
        while tasks or heap:
            if not heap:
                curr_time = max(curr_time, tasks[0][0])

            while tasks and tasks[0][0] <= curr_time:
                start, task_length, index = tasks.popleft()
                heapq.heappush(heap, (task_length, index))

            next_task_len, next_index = heapq.heappop(heap)
            res.append(next_index)

            curr_time += next_task_len

        return res
  1. Sort all tasks by their staring time
  2. If the heap is empty, start to run the task with smallest starting time, set the current time to that starting time
  3. Insert all tasks with starting time smaller than the finishing time of current task, and run the one with smallest task length next.

Time: O(nlogn) need to sort n tasks

Space: O(n)

muimi commented 3 years ago

思路

按照任务的开始时间进行排序，由于排序打乱任务序号，需要新建一个数组，追加一个任务序号的项。
之后使用优先队列，确保执行时间短的任务能够排在前面。优先队列中的入队顺序即为需要返回的结果。

代码

class Solution {
  public int[] getOrder(int[][] tasks) {
    int n = tasks.length;
    int[] res = new int[n];
    int[][] newTasks = new int[n][3];
    for (int i = 0; i < n; i++) {
      newTasks[i][0] = tasks[i][0]; // start time
      newTasks[i][1] = tasks[i][1]; // duration
      newTasks[i][2] = i; // task id
    }
    // 按照启动时间排序
    Arrays.sort(newTasks, (a, b) -> a[0] - b[0]);
    // 按照执行时间排序（执行时间相同时，按序号排序）
    PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]);

    int time = 0;
    int resIndex = 0, taskIndex = 0;
    while (resIndex < n) {
      while (taskIndex < n && newTasks[taskIndex][0] <= time) pq.offer(newTasks[taskIndex++]);
      if (pq.isEmpty()) {
        time = newTasks[taskIndex][0];
        continue;
      }
      int[] processTask = pq.poll();
      res[resIndex++] = processTask[2];
      time += processTask[1];
    }
    return res;
  }
}

复杂度

ghost commented 3 years ago

题目

  1. Single-Threaded CPU

思路

Priority Queue, need to think through how to build and use it for this question.

Sort the tasks using the enqueue time. Put all the enqueue time earlier than current time into the PQ Repeat and pop all the task in PQ

代码


class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:

        tasks = [(tasks[i][0], tasks[i][1], i)  for i in range(len(tasks))]
        tasks.sort()

        hq = []
        res = []
        time = 0
        idx = 0

        for _ in range(len(tasks)):
            if not hq:
                time = max(time, tasks[idx][0])

            while idx < len(tasks) and tasks[idx][0] <= time:
                heapq.heappush(hq, (tasks[idx][1],tasks[idx][2]))
                idx+=1

            curr = heapq.heappop(hq)
            time += curr[0]
            res.append(curr[-1])

        return res

复杂度

Space: O(NlogN) Time: O(N)

ninghuang456 commented 3 years ago 
 public int[] getOrder(int[][] tasks) {
        int len = tasks.length;
        int[][] tasksIdx = new int[len][3];
        for (int i = 0; i < len; i++) {
            tasksIdx[i][0] = tasks[i][0];
            tasksIdx[i][1] = tasks[i][1];
            tasksIdx[i][2] = i;
        }

        PriorityQueue<int[]> allTasks = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int[] task : tasksIdx)
            allTasks.offer(task);
        PriorityQueue<int[]> readyTasks = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]);

        int time = 0, i = 0;
        int[] res = new int[len];

        while (!allTasks.isEmpty() || !readyTasks.isEmpty()) {
            if (readyTasks.isEmpty())
                time = Math.max(time, allTasks.peek()[0]);
            while (!allTasks.isEmpty() && time >= allTasks.peek()[0])
                readyTasks.offer(allTasks.poll());

            int[] curTask = readyTasks.poll();
            res[i++] = curTask[2];
            time += curTask[1];
        }
        return res;
    }
zszs97 commented 3 years ago

开始刷题

题目简介

【Day 33 】2021-10-12 - 1834. 单线程 CPU

题目思路

题目代码

代码块

class Solution {
private:
    using PII = pair<int, int>;
    using LL = long long;

public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n = tasks.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            return tasks[i][0] < tasks[j][0];
        });

        vector<int> ans;
        // 优先队列
        priority_queue<PII, vector<PII>, greater<PII>> q;
        // 时间戳
        LL timestamp = 0;
        // 数组上遍历的指针
        int ptr = 0;

        for (int i = 0; i < n; ++i) {
            // 如果没有可以执行的任务，直接快进
            if (q.empty()) {
                timestamp = max(timestamp, (LL)tasks[indices[ptr]][0]);
            }
            // 将所有小于等于时间戳的任务放入优先队列
            while (ptr < n && tasks[indices[ptr]][0] <= timestamp) {
                q.emplace(tasks[indices[ptr]][1], indices[ptr]);
                ++ptr;
            }
            // 选择处理时间最小的任务
            auto&& [process, index] = q.top();
            timestamp += process;
            ans.push_back(index);
            q.pop();
        }

        return ans;
    }
};

复杂度

wangyifan2018 commented 3 years ago 
class Solution(object):
    def getOrder(self, tasks):
        """
        :type tasks: List[List[int]]
        :rtype: List[int]
        """
        n = len(tasks)
        indices = list(range(n))
        indices.sort(key=lambda x: tasks[x][0])

        ans = list()
        q = list()
        timestamp = 0
        ptr = 0

        for i in range(n):
            if not q:
                timestamp = max(timestamp, tasks[indices[ptr]][0])
            while ptr < n and tasks[indices[ptr]][0] <= timestamp:
                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))
                ptr += 1
            process, index = heapq.heappop(q)
            timestamp += process
            ans.append(index)
        return ans
Francis-xsc commented 3 years ago

思路

排序+优先队列 题解

代码


class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        int[][] nts = new int[n][3];
        for (int i = 0; i < n; i++) {
            nts[i] = new int[]{tasks[i][0], tasks[i][1], i};
        }
        Arrays.sort(nts, (a, b) -> a[0] - b[0]);
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) {
                return a[1] - b[1];
            }
            return a[2] - b[2];
        });
        int[] ans = new int[n];
        for (int time = 1, j = 0, idx = 0; idx < n; ) {
            while (j < n && nts[j][0] <= time) {
                q.add(nts[j++]);
            }
            if (q.isEmpty()) {
                time = nts[j][0];
            } else {
                int[] cur = q.poll();
                ans[idx++] = cur[2];
                time += cur[1];
            }
        }
        return ans;
    }
}

复杂度分析

Moin-Jer commented 3 years ago

思路

模拟时间线，对进队任务进行排序，并将该时间点之前到任务加入堆中，从堆中取出执行时间最短的任务

代码

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;

        List<Integer> idx = new ArrayList<>();
        for (int i = 0; i < n; i++) idx.add(i);
        idx.sort(Comparator.comparingInt(o -> tasks[o][0]));

        Queue<int[]> heap = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]);
            return Integer.compare(o1[1], o2[1]);
        });

        int[] res = new int[n];
        int k = 0, time = 0;
        for (int i = 0; i < n; i++) {
            if (heap.isEmpty())
                time = Math.max(time, tasks[idx.get(k)][0]);

            while (k < n && tasks[idx.get(k)][0] <= time) {
                heap.offer(new int[]{tasks[idx.get(k)][1], idx.get(k)});
                k++;
            }

            int[] t = heap.poll();
            time += t[0];
            res[i] = t[1];
        }

        return res;
    }
}

复杂度分析

Yufanzh commented 3 years ago

Intuition

The hard part for this question is to use minHeap data structure to store tasks waiting to be processed. Then the other part will just be to repeat what the question ask for in code.

Algorithm in python3

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        """
        step 1: sort tasks by enqueueTime, also need to record the original index
        """
        newTasks = [(task[0], task[1], i) for i, task in enumerate(tasks)]
        newTasks.sort()
        """
        step 2: create a minHeap dataStructure to store to-be-processed tasks, with key as processing time
        """
        backlog = [] # minHeap datastructure
        ans = [] # arraylist
        time = 0
        pos = 0
        """
        step 3: two conditions
        1. CPU is idle, no tasks in queue, directly fastforward time to the first task's enqueueTime;
        2. if CPU is not idle, while tasks enqueueTime smaller than curTime, push into heap; when the previous task finishes, popout the shortest processing time tasks
        and time will be increased by the processing time
        use ans array to record the processing task's original index
        """
        for _ in tasks:
            if not backlog:
                time = max(time, newTasks[pos][0])
            while pos < len(tasks) and newTasks[pos][0] <= time:
                heapq.heappush(backlog, (newTasks[pos][1], newTasks[pos][2]))
                pos += 1
            procTime, idx = heapq.heappop(backlog)
            time += procTime
            ans.append(idx)
        """step 4. when all tasks are processed, return ans
        """
        return ans

Complexity Analysis

JK1452470209 commented 3 years ago

思路

将数组转化为三维数组，把下标记录下。优先队列先按持续时间排序，再按任务编号进行排序

代码

class Solution {
    public int[] getOrder(int[][] ts) {
            int n = ts.length;
            // 将 ts 转存成 nts，保留任务编号
            int[][] nts = new int[n][3];
            for (int i = 0; i < n; i++) nts[i] = new int[]{ts[i][0], ts[i][1], i};
            // 根据任务入队时间进行排序
            Arrays.sort(nts, (a,b)->a[0]-b[0]);
            // 根据题意，先按照「持续时间」排序，再根据「任务编号」排序
            PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
                if (a[1] != b[1]) return a[1] - b[1];
                return a[2] - b[2];
            });
            int[] ans = new int[n];
            for (int time = 1, j = 0, idx = 0; idx < n; ) {
                // 如果当前任务可以添加到「队列」中（满足入队时间）则进行入队
                while (j < n && nts[j][0] <= time) q.add(nts[j++]);
                if (q.isEmpty()) {
                    // 如果当前「队列」没有任务，直接跳到下个任务的入队时间
                    time = nts[j][0];
                } else {
                    // 如果有可执行任务的话，根据优先级将任务出队（记录下标），并跳到该任务完成时间点
                    int[] cur = q.poll();
                    ans[idx++] = cur[2];
                    time += cur[1];
                }
            }
            return ans;
        }
}

复杂度

时间复杂度：O(NlogN)

空间复杂度：O(n)

kidexp commented 3 years ago

thoughts

首先构造一个新的list 包含原来的task的enqueue time 和 process time，再加上index

然后按照enqueue_time, process_time 和 index sort

遍历数组，记录cpu_time， 如果当前task的enqueue_time小于cpu_time 就把process_time,和下标加入heap，否则计算从heap里面pop出要加入的task，并且更新cpu_time

有一个特殊情况就是当前task的enqueue_time 大于 cpu_time 并且heap为空 那么我们就可以更新用当前时间cpu time

code

import heapq

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks_with_index = []
        for i, task in enumerate(tasks):
            tasks_with_index.append((task[0], task[1], i))
        tasks_with_index.sort()
        result = [tasks_with_index[0][-1]]
        i, end_time = 1, tasks_with_index[0][0] + tasks_with_index[0][1]
        heap = []
        while i <= len(tasks_with_index):
            if i < len(tasks_with_index) and tasks_with_index[i][0] <= end_time:
                # find a task can be added into heap
                heapq.heappush(
                    heap,
                    (
                        tasks_with_index[i][1],
                        tasks_with_index[i][-1],
                        tasks_with_index[i][0],
                    ),
                )
                i += 1
            elif heap:
                # no task can be added to heap, but we can handle heap
                next_task = heapq.heappop(heap)
                end_time += next_task[0]
                result.append(next_task[1])
            elif i < len(tasks_with_index):
                # we need cpu idle for some time to add new task
                result.append(tasks_with_index[i][-1])
                end_time = tasks_with_index[i][0] + tasks_with_index[i][1]
                i += 1
            else:
                break

        return result

complexity

Time O(nlgn)

Space O(n)