| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
中等 |
1797 |
第 237 场周赛 Q3 |
|
给你一个二维数组 tasks ，用于表示 n 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i 项任务将会于 enqueueTimei 时进入任务队列，需要 processingTimei 的时长完成执行。
现有一个单线程 CPU ，同一时间只能执行 最多一项 任务，该 CPU 将会按照下述方式运行：
- 如果 CPU 空闲，且任务队列中没有需要执行的任务，则 CPU 保持空闲状态。
- 如果 CPU 空闲，但任务队列中有需要执行的任务，则 CPU 将会选择 执行时间最短 的任务开始执行。如果多个任务具有同样的最短执行时间，则选择下标最小的任务开始执行。
- 一旦某项任务开始执行，CPU 在 执行完整个任务 前都不会停止。
- CPU 可以在完成一项任务后，立即开始执行一项新任务。
返回 CPU 处理任务的顺序。
示例 1：
输入：tasks = [[1,2],[2,4],[3,2],[4,1]]
输出：[0,2,3,1]
解释：事件按下述流程运行：
- time = 1 ，任务 0 进入任务队列，可执行任务项 = {0}
- 同样在 time = 1 ，空闲状态的 CPU 开始执行任务 0 ，可执行任务项 = {}
- time = 2 ，任务 1 进入任务队列，可执行任务项 = {1}
- time = 3 ，任务 2 进入任务队列，可执行任务项 = {1, 2}
- 同样在 time = 3 ，CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ，可执行任务项 = {1}
- time = 4 ，任务 3 进入任务队列，可执行任务项 = {1, 3}
- time = 5 ，CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ，可执行任务项 = {1}
- time = 6 ，CPU 完成任务 3 并开始执行任务 1 ，可执行任务项 = {}
- time = 10 ，CPU 完成任务 1 并进入空闲状态
示例 2：
输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
输出：[4,3,2,0,1]
解释：事件按下述流程运行：
- time = 7 ，所有任务同时进入任务队列，可执行任务项 = {0,1,2,3,4}
- 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
- time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
- time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
- time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
- time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
- time = 40 ，CPU 完成任务 1 并进入空闲状态
提示：
tasks.length == n1 <= n <= 1051 <= enqueueTimei, processingTimei <= 109
我们先将任务按照 enqueueTime 从小到大排序，接下来用一个优先队列（小根堆）维护当前可执行的任务，队列中的元素为 (processingTime, index)，即任务的执行时间和任务的编号。另外用一个变量
接下来我们模拟任务的执行过程。
如果当前队列为空，说明当前没有可执行的任务，我们将 enqueueTime 与当前时间 enqueueTime 小于等于
然后从队列中取出一个任务，将其编号加入答案数组，然后将
循环上述过程，直到队列为空，且所有任务都已经加入过队列。
时间复杂度
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
for i, task in enumerate(tasks):
task.append(i)
tasks.sort()
ans = []
q = []
n = len(tasks)
i = t = 0
while q or i < n:
if not q:
t = max(t, tasks[i][0])
while i < n and tasks[i][0] <= t:
heappush(q, (tasks[i][1], tasks[i][2]))
i += 1
pt, j = heappop(q)
ans.append(j)
t += pt
return ansclass Solution {
public int[] getOrder(int[][] tasks) {
int n = tasks.length;
int[][] ts = new int[n][3];
for (int i = 0; i < n; ++i) {
ts[i] = new int[] {tasks[i][0], tasks[i][1], i};
}
Arrays.sort(ts, (a, b) -> a[0] - b[0]);
int[] ans = new int[n];
PriorityQueue<int[]> q
= new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
int i = 0, t = 0, k = 0;
while (!q.isEmpty() || i < n) {
if (q.isEmpty()) {
t = Math.max(t, ts[i][0]);
}
while (i < n && ts[i][0] <= t) {
q.offer(new int[] {ts[i][1], ts[i][2]});
++i;
}
var p = q.poll();
ans[k++] = p[1];
t += p[0];
}
return ans;
}
}class Solution {
public:
vector<int> getOrder(vector<vector<int>>& tasks) {
int n = 0;
for (auto& task : tasks) task.push_back(n++);
sort(tasks.begin(), tasks.end());
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> q;
int i = 0;
long long t = 0;
vector<int> ans;
while (!q.empty() || i < n) {
if (q.empty()) t = max(t, (long long) tasks[i][0]);
while (i < n && tasks[i][0] <= t) {
q.push({tasks[i][1], tasks[i][2]});
++i;
}
auto [pt, j] = q.top();
q.pop();
ans.push_back(j);
t += pt;
}
return ans;
}
};func getOrder(tasks [][]int) (ans []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] })
q := hp{}
i, t, n := 0, 0, len(tasks)
for len(q) > 0 || i < n {
if len(q) == 0 {
t = max(t, tasks[i][0])
}
for i < n && tasks[i][0] <= t {
heap.Push(&q, pair{tasks[i][1], tasks[i][2]})
i++
}
p := heap.Pop(&q).(pair)
ans = append(ans, p.i)
t += p.t
}
return
}
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 { return h[i].t < h[j].t || (h[i].t == h[j].t && h[i].i < h[j].i) }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }