search

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

5 stars 0 forks source link

【Day 33 】2022-08-16 - 1834. 单线程 CPU #48

Closed azl397985856 closed 1 year ago

azl397985856 commented 2 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

ccslience commented 2 years 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()
        backlog = []
        time = 0
        ans = []
        pos = 0
        for _ in tasks:
            if not backlog:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans
luckyoneday commented 2 years ago

代码 js

const getOrder = function (tasks) {
    const queue = new MinPriorityQueue()
    tasks = tasks.map((task, index) => ({
        index,
        start: task[0],
        time: task[1]
    }))
    tasks.sort((a, b) => b.start - a.start)
    const answer = []
    let time = 0
    while (tasks.length > 0 || !queue.isEmpty()) {
        if (queue.isEmpty() && tasks[tasks.length - 1].start > time) {
            time = tasks[tasks.length - 1].start
        }

        while (tasks.length > 0) {
            if (tasks[tasks.length - 1].start <= time) {
                const task = tasks.pop()
                queue.enqueue(task, task.time * 100000 + task.index)
            } else {
                break
            }
        }

        const { element: task } = queue.dequeue()
        time += task.time
        answer.push(task.index)
    }
    return answer
}
Luckysq999 commented 2 years ago

class Solution { public int[] getOrder(int[][] tasks) { int n = tasks.length; int[] ans = new int[n]; int[][] extTasks = new int[n][3]; for(int i = 0; i < n; i++) { extTasks[i][0] = i; extTasks[i][1] = tasks[i][0]; extTasks[i][2] = tasks[i][1]; } Arrays.sort(extTasks, (a,b)->a[1] - b[1]); PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[2] == b[2] ? a[0] - b[0] : a[2] - b[2]); int time = 0; int ai = 0; int ti = 0; while(ai < n) { while(ti < n && extTasks[ti][1] <= time) { pq.offer(extTasks[ti++]);

        }
        if(pq.isEmpty()) {
            time = extTasks[ti][1];
            continue;
        }
        int[] bestFit = pq.poll();
        ans[ai++] = bestFit[0];
        time += bestFit[2];
    }
    return ans;
}

}

duke-github commented 2 years ago

思路

排序加优先队列

复杂度

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

代码

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;
    }
}
wsmmxmm commented 2 years ago

//PQ还是不是很熟练，怎么这么难哦 class Solution { public int[] getOrder(int[][] tasks) { if(tasks.length == 0 || tasks[0].length == 0){ return new int[]{}; } if(tasks.length == 1){ return new int[]{0}; } int n = tasks.length;

    PriorityQueue<Pair<int[], Integer>> bqueue = new PriorityQueue<>((a, b) -> a.getKey()[0] == b.getKey()[0] ? a.getKey()[1] - b.getKey()[1] : a.getKey()[0] - b.getKey()[0]);
    PriorityQueue<Pair<int[], Integer>> queue = new PriorityQueue<>((a, b) -> a.getKey()[1] == b.getKey()[1] ? a.getValue() - b.getValue() : a.getKey()[1] - b.getKey()[1]);

    for (int i = 0; i < n; i++) {
        bqueue.offer(new Pair<>(tasks[i], i));
    }

    queue.offer(bqueue.poll());

    int[] ret = new int[n];
    int cnt = 0, time = queue.peek().getKey()[0];

    while(!queue.isEmpty()){
        int pro = queue.peek().getKey()[1];
        ret[cnt++] = queue.poll().getValue();

        time += pro;

        while(!bqueue.isEmpty()  && bqueue.peek().getKey()[0] <= time){
            queue.offer(bqueue.poll());
        }

        while(!bqueue.isEmpty() && queue.isEmpty()){
            queue.offer(bqueue.poll());
        }
    }
    return ret;
}

}

zenwangzy commented 2 years ago 


// Time: O(NlogN)
// Space: O(N)
class Solution {
    typedef pair<int, int> T; // processing time, index
public:
    vector<int> getOrder(vector<vector<int>>& A) {
        priority_queue<T, vector<T>, greater<>> pq; // min heap of tasks, sorted first by processing time then by index.
        long N = A.size(), time = 0, i = 0; // `time` is the current time, `i` is the read pointer
        for (int i = 0; i < N; ++i) A[i].push_back(i); // append the index to each task
        sort(begin(A), end(A)); // sort the input array so that we can take the tasks of small enqueueTime first
        vector<int> ans;
        while (i < N || pq.size()) { // stop the loop when we exhausted the input array and the tasks in the heap.
            if (pq.empty()) {
                time = max(time, (long)A[i][0]); // nothing in the heap? try updating the current time using the processing time of the next task in array
            }
            while (i < N && time >= A[i][0]) { // push all the tasks in the array whose enqueueTime <= currentTime into the heap
                pq.emplace(A[i][1], A[i][2]);
                ++i;
            }
            auto [pro, index] = pq.top();
            pq.pop();
            time += pro; // handle this task and increase the current time by the processingTime
            ans.push_back(index);
        }
        return ans;
    }
};
adamw-u commented 2 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        sorted_task=[]
        for i in range(len(tasks)):
            sorted_task.append([tasks[i][0],tasks[i][1],i])
        sorted_task.sort()

        pq=[]
        res=[]
        i=0
        while i < len(sorted_task):
            if i < len(sorted_task) and not pq:
                cur_time = sorted_task[i][0]

            while i<len(sorted_task) and sorted_task[i][0]<=cur_time:
                heapq.heappush(pq, (sorted_task[i][1],sorted_task[i][2]))
                i+=1

            while pq:
                t = heappop(pq) 
                res.append(t[1])
                cur_time += t[0] 

                while i < len(sorted_task) and cur_time >= sorted_task[i][0]:
                    heappush(pq, (sorted_task[i][1], sorted_task[i][2]))
                    i += 1

        return res
frankelzeng commented 2 years ago

Idea

Use two heapq to store cache

Python Code

import heapq
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        all_task = [] # (enqueueTime, processTime, idx)
        ava_task = [] # (processTime, idx, enqueueTime)
        re = []
        for idx, task in enumerate(tasks):
            heapq.heappush(all_task, (task[0], task[1], idx))
        print("all_task", heapq.nsmallest(len(all_task), all_task))
        print("--------------")
        dummy = heapq.heappop(all_task)
        heapq.heappush(ava_task, (dummy[1], dummy[2], dummy[0]))
        while ava_task:
            print("ava_task", heapq.nsmallest(len(ava_task), ava_task))
            task = heapq.heappop(ava_task)
            re.append(task[1])
            print("re=", re)
            curr_time = task[0] + task[2]
            print("curr_time", curr_time)
            if all_task:
                new_task_eqtime = min(curr_time, all_task[0][0])
                print("new_task_eqtime", new_task_eqtime)
                print("all_task", heapq.nsmallest(len(all_task), all_task))
                print("--------------")
            else:
                continue
            while new_task_eqtime <= curr_time:
                new_ava = heapq.heappop(all_task)
                heapq.heappush(ava_task, (new_ava[1], new_ava[2], new_ava[0]))
                if all_task:
                    new_task_eqtime = all_task[0][0]
                else:
                    break
        # print(re)
        # print(heapq.nsmallest(len(all_task),all_task))
        return re
MaylingLin commented 2 years 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()
        backlog = []
        time = 0
        ans = []
        pos = 0
        for _ in tasks:
            if not backlog:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans
lbc546 commented 2 years ago

Heap

Python solution

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

        sorted_tasks = [(enqueue, process, idx) for idx, (enqueue, process) in enumerate(tasks)]
        sorted_tasks.sort()

        curr_time = 0
        task_index = 0

        while task_index < len(tasks) or next_task:
            if not next_task and curr_time < sorted_tasks[task_index][0]:
                curr_time = sorted_tasks[task_index][0]

            while task_index < len(sorted_tasks) and curr_time >= sorted_tasks[task_index][0]:
                _, process_time, original_index = sorted_tasks[task_index]
                heapq.heappush(next_task, (process_time, original_index))
                task_index += 1

            process_time, index = heapq.heappop(next_task)

            curr_time += process_time
            tasks_processing_order.append(index)

        return tasks_processing_order
Hacker90 commented 2 years ago

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

public: vector getOrder(vector<vector>& tasks) { int n = tasks.size(); vector 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;
}

};

whgsh commented 2 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
SunL1GHT commented 2 years ago

学习记录

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;
    }
}
SamLu-ECNU commented 2 years ago

思路

这题感觉要考虑的点还是蛮多的。

首先，使用一个数组indices来根据任务出现时间，从小到大记录任务编号，并使用指针ptr指示该数组中需要执行的下一个任务。

这里，我们使用变量timestamp记录当前时间戳。

之后，还需要一个优先队列pq装载到目前为止，所有接收到的任务，并以任务时间最短的作为根节点。

容易知道，所有任务执行完毕，整个优先队列中需要弹出n个任务，于是考虑每一次弹出的过程：

代码

import queue

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        indices = list(range(n))
        indices.sort(key=lambda x:tasks[x][0])
        timestamp = 0

        pq = queue.PriorityQueue()
        ptr = 0
        res = list()

        for i in range(n):
            if pq.empty():
                timestamp = max(timestamp, tasks[indices[ptr]][0])
            while ptr < n and tasks[indices[ptr]][0] <= timestamp:
                pq.put((tasks[indices[ptr]][1], indices[ptr]))
                ptr += 1
            time, index = pq.get()
            timestamp += time
            res.append(index)

        return res

复杂度

时间复杂度：$O(nlog(n))$

空间复杂度：$O(1)$

acoada commented 2 years ago

思路

模拟 + heapq

代码

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]))
                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

复杂度

ZOULUFENG commented 2 years 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()
        backlog = []
        time = 0
        ans = []
        pos = 0
        for _ in tasks:
            if not backlog:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans
gelxgx commented 2 years ago 
const getOrder = function (tasks) {
  const queue = new MinPriorityQueue()
  tasks = tasks.map((task, index) => ({
    index,
    start: task[0],
    time: task[1]
  }))
  tasks.sort((a, b) => b.start - a.start)
  const answer = []
  let time = 0
  while (tasks.length > 0 || !queue.isEmpty()) {
    // 队列为空，且没有任务能加入队列，直接跳过时间
    if (queue.isEmpty() && tasks[tasks.length - 1].start > time) {
      time = tasks[tasks.length - 1].start
    }

    // 向队列中加入可执行任务
    while (tasks.length > 0) {
      if (tasks[tasks.length -1].start <= time) {
        const task = tasks.pop()
        queue.enqueue(task, task.time * 100000 + task.index)
      } else {
        break
      }
    }

    // 执行任务
    const { element: task } = queue.dequeue()
    time += task.time
    answer.push(task.index)
  }
  return answer
}
Liuxy94 commented 2 years 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()
        backlog = []
        time = 0
        ans = []
        pos = 0
        for _ in tasks:
            if not backlog:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans

复杂度

时间：O(nlogn) 空间：O(1)

elaineKuo commented 2 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;
};

复杂度分析

Mryao1 commented 2 years ago 
class Solution {
    public int[] getOrder(int[][] tasks) {
        int[][] taskArray = new int[tasks.length][3];
        for (int i = 0; i < tasks.length; i++) {
            taskArray[i][0] = tasks[i][0];
            taskArray[i][1] = tasks[i][1];
            taskArray[i][2] = i;
        }
        Arrays.sort(taskArray, Comparator.comparingInt(o -> o[0]));
        PriorityQueue<int[]> queue = new PriorityQueue<>(((o1, o2) -> {
            if (o1[1] == o2[1]){
                return o1[2] - o2[2];
            }
            return o1[1] - o2[1];
        }));
        int[] rtn = new int[tasks.length];
        int index = 0;
        int time = taskArray[0][0];
        int i = 0;
        while (i < taskArray.length) {
            while (i < taskArray.length && taskArray[i][0] <= time){
                queue.offer(taskArray[i]);
                i++;
            }
            if (queue.isEmpty()){
                time = taskArray[i][0];
            } else {
                rtn[index++] = queue.peek()[2];
                time += queue.peek()[1];
                queue.poll();
            }
        }

        while (!queue.isEmpty()){
            rtn[index++] = queue.peek()[2];
            queue.poll();
        }
        return rtn;
    }
}
yibenxiao commented 2 years ago

【Day 33】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 time = 0;
        // 数组上遍历的指针
        int ptr = 0;

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

        return ans;
    }
};

复杂度

时间复杂度：O(NLogN)

空间复杂度：O(N)

Kaneyang commented 2 years ago

思路

模拟+堆heap

代码

from typing import List
import heapq

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> 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

复杂度分析

时间复杂度: O(nlogn)

空间复杂度: O(n)

chouqin99 commented 2 years 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() backlog = [] time = 0 ans = [] pos = 0 for _ in tasks: if not backlog: time = max(time, tasks[pos][0]) while pos < len(tasks) and tasks[pos][0] <= time: heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1])) pos += 1 d, j = heapq.heappop(backlog) time += d ans.append(j) return ans

nuomituxedo commented 2 years ago

参考了答案

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        # Sort based on min task processing time or min task index.
        next_task: List[Tuple[int, int]] = []
        tasks_processing_order: List[int] = []

        # Store task enqueue time, processing time, index.
        sorted_tasks = [(enqueue, process, idx) for idx, (enqueue, process) in enumerate(tasks)]
        sorted_tasks.sort()

        curr_time = 0
        task_index = 0

        # Stop when no tasks are left in array and heap.
        while task_index < len(tasks) or next_task:
            if not next_task and curr_time < sorted_tasks[task_index][0]:
                # When the heap is empty, try updating curr_time to next task's enqueue time. 
                curr_time = sorted_tasks[task_index][0]

            # Push all the tasks whose enqueueTime <= currtTime into the heap.
            while task_index < len(sorted_tasks) and curr_time >= sorted_tasks[task_index][0]:
                _, process_time, original_index = sorted_tasks[task_index]
                heapq.heappush(next_task, (process_time, original_index))
                task_index += 1

            process_time, index = heapq.heappop(next_task)

            # Complete this task and increment curr_time.
            curr_time += process_time
            tasks_processing_order.append(index)

        return tasks_processing_order
neado commented 2 years ago 
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;
    }
}
andyyxw commented 2 years ago 
/**
 * Algorithm: MinPriorityQueue
 */
function getOrder(tasks: number[][]): number[] {
  const queue = new MinPriorityQueue()
  const taskss = tasks.map((task, index) => ({
    index,
    start: task[0],
    time: task[1]
  }))
  taskss.sort((a, b) => b.start - a.start)
  const answer: number[] = []
  let time = 0
  while (taskss.length|| !queue.isEmpty()) {
    if (queue.isEmpty() && taskss[taskss.length - 1].start > time) {
      time = taskss[taskss.length - 1].start
    }

    while (taskss.length) {
      if (taskss[taskss.length -1].start <= time) {
        const task = taskss.pop()
        queue.enqueue(task, task.time * 100000 + task.index)
      } else {
        break
      }
    }

    const { element: task } = queue.dequeue()
    time += task.time
    answer.push(task.index)
  }
  return answer
};
yingchehu commented 2 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        # 依照 heap 的排序優先序調整元素順序
        # (processingTime, index, enqueueTime)
        tasks = [(task[1], i, task[0]) for i, task in enumerate(tasks)]
        # 依照可執行時間排序
        tasks.sort(key=itemgetter(2))
        # 初始時間
        t = tasks[0][2]
        # 將第一批 task 進 heap
        available = []
        while tasks and tasks[0][2] <= t:
            task = tasks.pop(0)
            heapq.heappush(available, task)

        ans = []
        while available or tasks:
            if available:
                execTask = heapq.heappop(available)
                t += execTask[0]
                ans.append(execTask[1])
            else:
                # 如果 heap 沒有東西了，直接跳到下一個可執行 task 的時間點
                t = tasks[0][2]               
            while tasks and tasks[0][2] <= t:
                availTask = tasks.pop(0)
                heapq.heappush(available, availTask)                     
        return ans
Irenia111 commented 2 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;
    }
}
ZhongXiangXiang commented 2 years ago

思路

先根据入队时间排序，默认当前时间为第一个入队的入队时间，并执行第一个任务，当第一个任务执行完，当前时间加上第一个任务执行的时间为当前时间。遍历排好序的tasks，将小于当前时间的任务入队，构建小顶堆，每次堆顶出队执行，并重新计算当前时间，重复之前的操作。

代码

/**
 * @param {number[][]} tasks
 * @return {number[]}
 */
var getOrder = function(tasks) {
    tasks.forEach((item, i) => item.push(i))
    tasks.sort((a, b) => a[0] - b[0])

    let stack = []
    let curTime = tasks[0][0]
    let i = 0
    let res = []
    while (i < tasks.length) {
        while (i < tasks.length && tasks[i][0] <= curTime) {
            stack.push(tasks[i])
            shiftUp(stack, stack.length - 1)
            i++
        }

        if (stack.length === 0) {
            // 没有任务
            stack.push(tasks[i])
            curTime = tasks[i][0]
            shiftUp(stack, stack.length - 1)
            i++
            continue
        }

        // 执行
        const curTask = stack[0]
        res.push(curTask[2])
        curTime += curTask[1]
        if (stack.length === 1) {
            stack.pop()
            continue
        }
        stack[0] = stack.pop()
        shiftDown(stack, 0)
    }

    while (stack.length) {
        const curTask = stack[0]
        res.push(curTask[2])
        if (stack.length === 1) {
            stack.pop()
            continue
        }
        stack[0] = stack.pop()
        shiftDown(stack, 0)
    }

    return res
};

function shiftUp(arr, i) {
    let parentI = (i - 1) >> 1
    while (parentI >= 0 && (arr[parentI][1] > arr[i][1] || (arr[parentI][1] === arr[i][1] && arr[parentI][2] > arr[i][2]))) {
        // 需执行时间更小，或执行时间相同但下标更小
        swap(arr, i, parentI)
        i = parentI
        parentI = (i - 1) >> 1
    }
}
function swap(arr, i1, i2) {
    [arr[i1], arr[i2]] = [arr[i2], arr[i1]]
}
function shiftDown (arr, i) {
    const n = arr.length
    while (i < n) {
        let minI = i
        let leftI = (i << 1) + 1
        let rightI = leftI + 1
        if (leftI < n && (arr[leftI][1] < arr[minI][1] || (arr[leftI][1] === arr[minI][1] && arr[leftI][2] <= arr[minI][2]))) {
            minI = leftI
        }
        if (rightI < n && (arr[rightI][1] < arr[minI][1] || (arr[rightI][1] === arr[minI][1] && arr[rightI][2] < arr[minI][2]))) {
            minI = rightI
        }
        if (minI === i) {
            break
        }
        swap(arr, i, minI)
        i = minI
    }
}

复杂度

时间：O(nlogn), 排序O(nlogn), 小顶堆O(nlogn) 空间：O(n), 保存堆

andyyxw commented 2 years ago 
/**
 * Algorithm: Simulation + PriorityQueue
 */
function getOrder(tasks: number[][]): number[] {
  const taskss = tasks.map((task, index) => ({
    index,
    start: task[0],
    time: task[1]
  })).sort((a, b) => b.start - a.start) // 如果taskss的start按照从小到大排列，那么下面每次都要shift()，如果换成从大到小排列每次只需要pop()，时间复杂度更优
  const queue = new MinPriorityQueue({
    // 因为任务最大数量为10^5，所有优先级要这么处理保持唯一（time优先，其次index优先）
    priority: (task) => task.time * Math.pow(10, 5) + task.index
  })
  const answer: number[] = []
  let time = 0
  while (taskss.length || !queue.isEmpty()) {
    if (queue.isEmpty() && time < taskss[taskss.length - 1].start) time = taskss[taskss.length - 1].start
    while (taskss.length && taskss[taskss.length - 1].start <= time) queue.enqueue(taskss.pop())
    const task = queue.dequeue().element
    time += task.time
    answer.push(task.index)
  }
  return answer
};
kernelSue commented 2 years ago 
class Solution {
    public int[] getOrder(int[][] tasks) {
        if(tasks.length == 1)  return new int[]{0};

        //[0]:index  [1]:enqueueTimei
        PriorityQueue<int[]> heap1 = new PriorityQueue<>((o1, o2) -> {
            return o1[1]- o2[1];
        });
        //[0]:index  [1]:processingTimei
        PriorityQueue<int[]> heap2 = new PriorityQueue<>((o1, o2) -> {
            if(o1[1] != o2[1])  return o1[1]- o2[1];
            else  return o1[0] - o2[0];
        });
        for(int i = 0; i < tasks.length; i++)
            heap1.offer(new int[]{i, tasks[i][0]});
        //start processing tasks
        int[] res = new int[tasks.length];
        int time = 1;
        int index = 0;
        while(!heap1.isEmpty() || !heap2.isEmpty()){
            while(!heap1.isEmpty() && heap2.isEmpty() && heap1.peek()[1] > time)  time++;
            while(!heap1.isEmpty() && heap1.peek()[1] <= time){
                int j = heap1.poll()[0];
                heap2.offer(new int[]{j, tasks[j][1]});
            }
            res[index++] = heap2.peek()[0];
            time += tasks[heap2.peek()[0]][1];
            heap2.poll();
        }
        return res;
    }
}
DuanYaQi commented 2 years ago

Day 33. 1834. 单线程 CPU

思路

最开始加入相同时间的进入队列，然后执行完一个任务，加入满足时间的任务，按

  1. 执行时间最短
  2. 下标最小

的优先顺序进入小顶堆。注意写 cmp 的时候，满足条件的沉底而不是升顶。注意空闲时间的跳跃处理

class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n = tasks.size(); 
        vector<vector<int>> newtasks = tasks;
        for (int i = 0; i < n; ++i) {
            newtasks[i].push_back(i);
        }

        sort(newtasks.begin(), newtasks.end()); // 默认第一个元素升序排

        auto cmp2 = [] (const vector<int> &v1, const vector<int> &v2) {
            if (v1[1] == v2[1]) return v1[2] > v2[2];
            return v1[1] > v2[1];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp2)> pq(cmp2);

        int i = 0;
        long long nowTime = newtasks[i][0];
        for (; i < n && newtasks[i][0] <= nowTime; i++) {
            pq.push(newtasks[i]);
        }

        vector<int> res;
        while (pq.size()) {
            auto cur = pq.top(); pq.pop();
            res.push_back(cur[2]);

            if (pq.empty() && i < n) {
                nowTime = nowTime + cur[1] > newtasks[i][0] ? 
                            nowTime + cur[1] : newtasks[i][0]; //跳过空闲的时间
            } else {
                nowTime += cur[1];
            }

            while (i < n && newtasks[i][0] <= nowTime) {
                pq.push(newtasks[i++]);
            }
        }

        return res;
    }
};
  • 时间复杂度: O(NlogN)，排序的时间复杂度 O(nlogn)，优先队列插入为 O(logn)，插入 N 个节点。
  • 空间复杂度: O(N)，队列长度

模板

无模板

yopming commented 2 years ago 
// 先把所有tasks按照enqueueTime来排序，使用额外的vector来存储tasks的index（比较enqueueTime）
// 开始执行的时候，如果当前队列没有任务，则时间快进到第一个任务的enqueueTime（index为0的那个）
// 然后把所有enqueueTime小于等于当前任务的enqueueTime的任务放入队列
// 取队列顶部，记录index，然后当前时钟加上队列顶部任务的processingTime

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

class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
      int n = tasks.size();
      std::vector<int> indices; // if use std::iota, declare size of the vector
      for (int i = 0; i < n; i++) {
        indices.push_back(i);
      }
      // sort by enqueueTime
      // then, tasks[indices[i]][0] <= tasks[indices[i+1]][0]
      std::sort(indices.begin(), indices.end(), [&](int i, int j) {
        return tasks[i][0] < tasks[j][0];
      });
      
      std::vector<int> result;
      std::priority_queue<
        std::pair<int, int>, 
        std::vector<std::pair<int, int>>, 
        std::greater<std::pair<int, int>>
      > q;
      
      long long time = 0;
      int ptr = 0;
      
      for (int i = 0; i < n; i++) {
        // if no task, skip to the first available enqueueTime
        if (q.empty()) {
          time = std::max(time, (long long)tasks[indices[ptr]][0]);
        }
        
        // put all tasks whose enqueueTime is less or same into q
        // put [processingTime, index] into queue
        while (ptr < n && tasks[indices[ptr]][0] <= time) {
          q.emplace(tasks[indices[ptr]][1], indices[ptr]);
          ptr++;
        }
        
        // choose the task with minimum processing Time
        auto [processingTime, index] = q.top();
        time += processingTime;
        result.push_back(index);
        q.pop();
      }
      
      return result;
    }
};
lzyxts commented 2 years ago

class Solution: def getOrder(self, tasks: List[List[int]]) -> List[int]: res, queue = [], [] tasks = sorted(enumerate(tasks), key = lambda x: (x[1][0], x[1][1], x[0]))

    curtime = tasks[0][1][0]
    i = 0

    while len(res) < len(tasks):
        while i < len(tasks) and tasks[i][1][0] <= curtime:
            heapq.heappush(queue, (tasks[i][1][1], tasks[i][0]))
            i+=1

        if queue:
            time, idx = heapq.heappop(queue)
            curtime += time
            res.append(idx)

        else:
            curtime = tasks[i][1][0]

    return res
maoting commented 1 year ago

思路：

自己实现堆居然超时了 堆

代码：

// https://mp.weixin.qq.com/s/N3GsQk--xDxj2U6DGMRbkw
class Heap {
    constructor(arr = []) {
        this.size = arr.length;
        this.heap = new Array(arr.length + 1);
        // 数组从 1 开始存储数据
        arr.forEach((item, i) => {
            this.heap[i+1] = item;
        })
    }
    setCompare(comFn = ((a, b) => (b - a))) {
        this.compare = (x, y) => {
            return comFn.apply(this, [this.heap, x, y])
        };
    }
    // 是要上浮的元素，从树的底部开始上浮
    shiftUp(i) {
        // 如果小于双亲，与双亲交换
        while ((i >> 1) > 0) {
            // if (temp[1] < this.heap[i >> 1][1]) {
            if (this.compare(i, i>>1)) {
                // 指向交换的位置，继续向上比较，一直上浮到跟节点
                let temp = this.heap[i];
                this.heap[i] = this.heap[i >> 1];
                this.heap[i >> 1] = temp;
                i >>= 1;
            } else {
                break;
            }
        }
    }
    shiftDown(i) {
        let temp = this.heap[i];
        // 如果有左孩子
        while (i * 2 <= this.size) {
            // minChild 是获取更小的子节点的索引并返回
            let child = i * 2;
            // j!=size 判断当前元素是否包含右节点 
            // 如果有右孩子且比右孩子比左孩子小(找一个小的)
            // if (child != this.size && this.heap[child+1][1] < this.heap[child][1]) {
            if (child != this.size && this.compare(child+1, child)) {
                child ++; // j指向右孩子
            }
            // if (temp[1] < this.heap[child][1]) {
            if (this.compare(i, child)) {
                break;
            } else {
                this.heap[i] = this.heap[child];
                i = child;
            }
            // x指向交换后的新位置，继续向下比较，一直下沉到叶子
            this.heap[i] = temp;
        }
    }
    // 构建堆(初始化堆)
    buildHeap() {
        // 从最后一个分支节点n/2开始下沉调整为堆，直到第一个节点
        for (let i = this.heap.length >> 1; i >= 1; i--) {
            this.shiftDown(i);
        }
    }
    // 出堆：取出第一个元素，然后把最后一个元素放到对顶并下沉
    pop() {
        const popVal = this.heap[1];
        this.heap[1] = this.heap[this.size];
        this.heap = this.heap.slice(0, this.size);
        this.size--;
        this.shiftDown(1);
        return popVal;
    }
    // 入堆：放在最后一个位置，然后上浮
    push(val) {
        // 长度加1后，将新元素放入尾部
        this.heap[++this.size] = val;
        this.shiftUp(this.size);
    }
    isEmpty() {
        return !this.size;
    }
}

var getOrder = function(tasks) {
    // 为每个 task 添加一个索引属性并排序
    tasks.forEach((v, i) => v.push(i));
    // 排序
    tasks.sort((a, b) => a[0] - b[0]);
    let n = tasks.length;
    let ans = [];
    let queue = new Heap([]);
    queue.setCompare((heap, x, y)=> {
        // 第一优先级为执行时间，第二优先级为任务索引
        return heap[x][1] !== heap[y][1]
          ? heap[x][1] < heap[y][1]
          : heap[x][2] < heap[y][2]
    });
    // 时间戳
    let timestamp = 0
    // 数组上遍历的指针
    let ptr = 0;

    for (let i = 0; i < tasks.length;i++) {
        // 如果没有可以执行的任务，直接快进
        if (queue.isEmpty() && tasks[i][0] > timestamp) {
            timestamp = tasks[i][0];
        }

        // 将所有小于等于时间戳的任务放入优先队列
        while (ptr < n && tasks[ptr][0] <= timestamp) {
            queue.push(tasks[ptr]);
            ptr++;
        }
        // 选择处理时间最小的任务
        const node = queue.pop();
        timestamp += node[1];
        ans.push(node[2]);
    }
    return ans;
};

复杂度分析