Skip to main content

621. Task Scheduler

分析


  • 思考差异

题解

/**
["A","A","A","B","B","B"]
n = 2

转换为频率
[3, 3] -> maxHeap 利用高频率优先策略
[] -> queue 等待队列
0 -> time 初始化时间


1. 取出 3,执行任务 3 - 1 = 2, 任务消耗时间为1,当前时间为 0 + 1 = 1, 组合 QueueTask{time + n = 1 + 2, 2}
前置,看等待队列中是否存在符合当前时间的 task

*/
interface QueueTask {
minTimeCanExec: number
frequency: number
}

class Maxheap {
// [1, 2, 3]
heap: number[] = []

constructor(nums = [] as number[]) {
this.heap = nums.sort((a, b) => a - b)
}

// pop the top element
pop(): number | undefined {
return this.heap.pop()
}

// push num to the head
push(num: number) {
const idx = this.heap.findIndex((v) => v > num)
if (idx === -1) {
this.heap.push(num)
} else {
this.heap.splice(idx, 0, num)
}
}

get length(): number {
return this.heap.length
}
}

function leastInterval(tasks: string[], n: number): number {
const tempMemo = {} as Record<string, number>
for (const task of tasks) {
tempMemo[task] = tempMemo[task] ? tempMemo[task] + 1 : 1
}
const maxHeap = new Maxheap(Object.values(tempMemo))
const queue: QueueTask[] = []
let time = 0
while (maxHeap.length || queue.length) {
time += 1
if (maxHeap.length) {
const taskFrequency = maxHeap.pop()
if (taskFrequency - 1 > 0) {
queue.push({
minTimeCanExec: time + n,
frequency: taskFrequency - 1
})
}
}
if (queue.length && time === queue[0].minTimeCanExec) {
maxHeap.push(queue[0].frequency)
queue.shift()
}
}

return time
};

未通过

/**
["A","A","A","B","B","B"]
n = 2

转换为频率
[3, 3] -> maxHeap 利用高频率优先策略
[] -> queue 等待队列
0 -> time 初始化时间


1. 取出 3,执行任务 3 - 1 = 2, 任务消耗时间为1,当前时间为 0 + 1 = 1, 组合 QueueTask{time + n = 1 + 2, 2}
前置,看等待队列中是否存在符合当前时间的 task

*/
interface QueueTask {
minTimeCanExec: number
frequency: number
}

class Maxheap {
// [1, 2, 3]
heap: number[] = []

constructor(nums = [] as number[]) {
this.heap = nums.sort((a, b) => a - b)
}

// pop the top element
pop(): number | undefined {
return this.heap.pop()
}

// push num to the head
push(num: number) {
const idx = this.heap.findIndex((v) => v > num)
if (idx === -1) {
this.heap.push(num)
} else {
this.heap.splice(idx, 0, num)
}
}

get length(): number {
return this.heap.length
}
}

function leastInterval(tasks: string[], n: number): number {
if (n === 0) {
return tasks.length
}
const tempMemo = {} as Record<string, number>
for (const task of tasks) {
tempMemo[task] = tempMemo[task] ? tempMemo[task] + 1 : 1
}
const maxHeap = new Maxheap(Object.values(tempMemo))
const queue: QueueTask[] = []
let time = 0
while (maxHeap.length || queue.length) {
time += 1
while (queue.length && time === queue[0].minTimeCanExec) {
maxHeap.push(queue[0].frequency)
queue.shift()
}
if (maxHeap.length) {
const taskFrequency = maxHeap.pop()
if (taskFrequency - 1 > 0) {
queue.push({
minTimeCanExec: time + n,
frequency: taskFrequency - 1
})
}
}
}

return time
};