class Solution {
public:
vector<int> getOrder(vector<vector<int>>& tasks) {
}
};
1834. 单线程 CPU
给你一个二维数组 tasks ，用于表示 n 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。
现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：
返回 CPU 处理任务的顺序。
示例 1：
输入：tasks = [[1,2],[2,4],[3,2],[4,1]]
输出：[0,2,3,1]
解释：事件按下述流程运行：
- time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}
- 同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}
- time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}
- time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}
- 同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}
- time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}
- time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}
- time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}
- time = 10 ，CPU 完成任务 1 并进入空闲状态
示例 2：
输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
输出：[4,3,2,0,1]
解释：事件按下述流程运行：
- time = 7 ，所有任务同时进入任务队列，可执行任务项 = {0,1,2,3,4}
- 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
- time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
- time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
- time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
- time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
- time = 40 ，CPU 完成任务 1 并进入空闲状态
提示：
tasks.length == n1 <= n <= 1051 <= enqueueTimei, processingTimei <= 109原站题解
rust 解法, 执行用时: 56 ms, 内存消耗: 9.5 MB, 提交时间: 2023-09-13 16:36:06
impl Solution {
pub fn get_order(tasks: Vec<Vec<i32>>) -> Vec<i32> {
use std::cmp::Reverse as rvs;
use std::collections::BinaryHeap;
let mut tasks: Vec<_> = tasks
.into_iter()
.enumerate()
.map(|(i, t)| (t[0], t[1], i as i32))
.collect();
tasks.sort_unstable();
let mut ans = Vec::with_capacity(tasks.len());
let mut cur = i32::MIN;
let mut wait = BinaryHeap::with_capacity(tasks.len());
let mut i = 0;
loop {
if wait.is_empty() && i < tasks.len() && cur < tasks[i].0 {
cur = tasks[i].0;
}
while i < tasks.len() && cur >= tasks[i].0 {
wait.push((rvs(tasks[i].1), rvs(tasks[i].2)));
i += 1;
}
if let Some((rvs(t), rvs(idx))) = wait.pop() {
cur += t;
ans.push(idx);
} else {
break ans;
}
}
}
// 解法二
pub fn get_order2(tasks: Vec<Vec<i32>>) -> Vec<i32> {
use std::collections::BinaryHeap;
let (mut i, mut s, n) = (0, 0, tasks.len());
let mut id: Vec<usize> = (0..n).collect();
id.sort_by(|&a, &b| tasks[a][0].cmp(&tasks[b][0]));
let mut h: BinaryHeap<(i32, i32)> = BinaryHeap::new();
let mut ans: Vec<i32> = vec![];
while i < n || !h.is_empty() {
if h.is_empty() {
let j = id[i];
s = tasks[j][0];
h.push((-tasks[j][1], -(j as i32)));
i += 1;
} else {
let x = h.pop();
if x != None {
ans.push(-x.unwrap().1 as i32);
s += -x.unwrap().0;
}
}
while i < n && tasks[id[i]][0] <= s {
let j = id[i];
h.push((-tasks[j][1], -(j as i32)));
i += 1;
}
}
ans
}
}
python3 解法, 执行用时: 532 ms, 内存消耗: 54.7 MB, 提交时间: 2023-09-13 16:33:28
# 模拟，最小堆
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
java 解法, 执行用时: 99 ms, 内存消耗: 85.5 MB, 提交时间: 2023-09-13 16:32:39
class Solution {
class Task{
int id;
int enqueueTime;
int processingTime;
public Task(int id, int enqueueTime, int processingTime){
this.id = id;
this.enqueueTime = enqueueTime;
this.processingTime = processingTime;
}
}
public int[] getOrder(int[][] tasks) {
int len = tasks.length;
List<Task> taskList = new ArrayList<>();
for(int i=0; i<len; i++){
taskList.add(new Task(i, tasks[i][0], tasks[i][1]));
}
//按入队时间排序
Collections.sort(taskList, (t1,t2) -> t1.enqueueTime - t2.enqueueTime);
//利用最小堆获取下个要执行的任务
PriorityQueue<Task> minHeap = new PriorityQueue<>((t1,t2) -> {
if(t1.processingTime == t2.processingTime){
//当执行时间相同时，根据id升序
return t1.id - t2.id;
}else{
//当执行时间不同时，根据执行时间升序
return t1.processingTime - t2.processingTime;
}
});
long now = 0;//当前时间，使用long防止int溢出
int i = 0;//taskList的坐标
int[] ret = new int[len];
int p = 0;//ret的坐标
while(i<len){//taskList中还有任务没有放入堆时
//将所有入队时间<=当前时间的任务放入堆中
while(i<len && taskList.get(i).enqueueTime<=now){
minHeap.offer(taskList.get(i));
i++;
}
//当堆中没有任务，即当前cpu空闲
if(minHeap.isEmpty()){
//当前时间置为任务队列taskList中入队时间最小的时间
now = (long)taskList.get(i).enqueueTime;
while(i<len && taskList.get(i).enqueueTime<=now){
minHeap.offer(taskList.get(i));
i++;
}
}
//此时保证堆中有任务待执行，取出执行即可
Task task = minHeap.poll();
ret[p++] = task.id;
now += task.processingTime;
}
//当任务列表taskList中的全部任务已经入堆
while(!minHeap.isEmpty()){
//按顺序取出任务执行即可
ret[p++] = minHeap.poll().id;
}
return ret;
}
}
golang 解法, 执行用时: 416 ms, 内存消耗: 19.2 MB, 提交时间: 2023-09-13 16:31:36
// 按进入时间排序。遍历任务数组，每次至多执行一个任务，
// 然后将所有进入时间不超过当前时间 cur 的任务加入堆中。
type pair struct{ t, i int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) 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 hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func (h *hp) push(v pair) { heap.Push(h, v) }
func (h *hp) pop() pair { return heap.Pop(h).(pair) }
func getOrder(a [][]int) (ans []int) {
for i := range a {
a[i] = append(a[i], i)
}
sort.Slice(a, func(i, j int) bool { return a[i][0] < a[j][0] })
h := &hp{}
for i, cur, n := 0, 0, len(a); i < n; {
if h.Len() > 0 {
p := h.pop()
ans = append(ans, p.i)
cur += p.t
}
if h.Len() == 0 && cur < a[i][0] {
cur = a[i][0]
}
for ; i < n && a[i][0] <= cur; i++ {
h.push(pair{a[i][1], a[i][2]})
}
}
for h.Len() > 0 {
ans = append(ans, h.pop().i)
}
return
}