621. Task Scheduler

Abstraction

Entity & State:
- All task label: remaining count, next execution time.
- Container (CPU): idle or executing task label
- Time
Transition: Time elapsed, if CPU is idle, we pick one task to execute.
- task[i]: remaining count - 1, update next execution time.
- CPU: idle → executing
Constraint: If task A is executed at time t, then next time to execute is t + n + 1.
Goal: Find the minimum time to complete all tasks.
Abstraction:
- To find the minimum time, we aim to fill in the task within on interval as many as possible in terms of the constraint.
- Since we can't arrange the same task within the same interval, we break the timeline by one interval, fill in with different task.
```
tasks = [A, A, A, B, B, C], n = 5
_, _, _, _, _ // The slots in one interval
A  B  C       
A  B
A
```
- We should assign the most frequently task first greedily. If we assign the low-frequent task first, we will run out of them and there are lots of high-frequent tasks at the last. And we have to wait more “blank” interval (CPU becomes more idle) to complete those high-frequent tasks.
```
tasks = [A, A, B], n = 2
// Pick A first, we can fill in B during 2 A.
A, B, _, A = 4
// Pick B first, there is no B to fill in during 2 A.
B, A, _, _, A = 5

tasks = [A, A, A, B], n = 2
// Pick A first
A, B, _, A, _, _, A
// Pick B first
B, A, _, _, A, _, _, A
```

Brute Force

WA: findMostFrequentTasks(taskCounts) 只有找目前頻率最高的，但是沒考慮到頻率最高的目前可能在冷凍期，使得 CPU 在那邊空等。

fun leastInterval(tasks: CharArray, n: Int): Int {
    val taskCounts = IntArray(26)
    for (c in tasks) {
        taskCounts[c - 'A']++
    }
    val taskNextTime = IntArray(26)
    var time = 0
    while (taskCounts.isNotEmpty()) {
        val taskIndex = findMostFrequentTasks(taskCounts)
        if (taskIndex != -1 && taskNextTime[taskIndex] <= time) {
            taskCounts[taskIndex]--
            taskNextTime[taskIndex] = time + n + 1
        }
        time++
    }
    return time
}

private fun IntArray.isNotEmpty(): Boolean {
    for (v in this) {
        if (v > 0) return true
    }
    return false
}

private fun findMostFrequentTasks(taskCounts: IntArray): Int {
    var freq = 0
    var taskIndex = -1
    for (i in taskCounts.indices) {
        if (taskCounts[i] >= freq) {
            freq = taskCounts[i]
            taskIndex = i
        }
    }
    return taskIndex
}

正確的找法應該要同時考慮最高頻而且不是在冷凍期。

fun leastInterval(tasks: CharArray, n: Int): Int {
    val taskCounts = IntArray(26)
    for (c in tasks) {
        taskCounts[c - 'A']++
    }
    val taskNextTime = IntArray(26)
    var time = 0
    while (taskCounts.isNotEmpty()) {
        val taskIndex = findMostFrequentAvailableTasks(taskCounts, taskNextTime, time)
        if (taskIndex != -1) {
            taskCounts[taskIndex]--
            taskNextTime[taskIndex] = time + n + 1
        }
        time++
    }
    return time
}

private fun IntArray.isNotEmpty(): Boolean {
    for (v in this) {
        if (v > 0) return true
    }
    return false
}

private fun findMostFrequentAvailableTasks(taskCounts: IntArray, taskNextTime: IntArray, time: Int): Int {
    var freq = 0
    var taskIndex = -1
    for (i in taskCounts.indices) {
        if (taskCounts[i] >= freq && taskNextTime[i] <= time) {
            freq = taskCounts[i]
            taskIndex = i
        }
    }
    return taskIndex
}

Time complexity: O(frequency * interval)
Space complexity: O(1)

Bottleneck

We have to simulate the time elapsed, in the worst case, tasks = [A, A, A], n = 1000, it’s a waste to simulate the time between A

A, _, _, ..., _, A
   |-----------| // waste

Pattern Recognition

Since we choose the most frequent available task in each interval, and use non-most frequent available tasks to fill in in the interval, we can calculate the frequency of each task, find the most frequent one. → Heap for most frequent task in each interval

n = 4
A, _, _, _, _
A, _, _, _, _  // (3 - 1) * (4 + 1) Correct!
A, ?  ?        // +1 or ??

[A, A, A, B, B, C], n = 1
A: 3, B: 2, C: 1
[A, A, A, B, B, B, C], n = 1
A: 3, B: 3, C: 1
A, _
A, _
A, _

Stuck

Brute Force
我有想到可以依照最高頻的任務去切分區段，但是無法成功用 heap 去模擬這種切分安排任務。
Mathematical solution
What if the number of most frequent task is more than intervals, like [A, B, C, D] are most frequent tasks, but interval is only 1.
```
A, B
A, B
C, D
C, D
```

Heap

The same task cannot be executed within n intervals. So the idea is to arrange the same task in the following way:

// n = 2
A, _, _, A, _, _, A, X, X // We don't have to insert the idle interval at the end if there is no other tasks
   ^^^^     ^^^^ 
   // We can insert the other tasks in between
   B,       B,       B, ...
      C, 	   C,       C, ...

To find the least interval, we can start arranging the tasks with the most frequency, and insert the other tasks in between with n intervals. So in the interval n, we pick the tasks by frequency at most n times, if there is no enough n tasks, we can insert the idle interval at the end, except the last interval.

// n = 2, frequency: A > B > C
 |-- n ---|-- n ---|-- n --|
 A, B, C, A, _, _, A
    ^^^^              		// Insert other tasks in between
	         ^^^^^			// Insert the idle interval at the end
			         ^^^^   // Don't insert the idle interval at the end if there is no other tasks

// Examples
tasks = {A: 3, B: 2, C: 1}
A, _, _, A, _, _, A
   B  C     B

tasks = {A: 3, B: 3}
A, _, _, A, _, _, A, _
   B        B        B

fun leastInterval(tasks: CharArray, n: Int): Int {
	val count = IntArray(26)
	for (c in tasks) {
		count[c - 'A']++
	}       
	val heap = PriorityQueue<Int>() { i1, i2 -> 
		val count1 = count[i1]
		val count2 = count[i2]
		count2 - count1
	}
	(0 until count.size).forEach {
		if (count[it] > 0) heap.add(it)
	}
	var intervals = 0
	while (heap.isNotEmpty()) {
		// We start to insert tasks in the interval `n + 1`
		// +1 for the first task + `n` intervals
		// [A, _, _, _] [A, _, _, _] [A, _, _, _]
		//  1 + n = 3
		val executedList = mutableListOf<Int>()
		// Iterate `n + 1` times
		while (executedList.size <= n && heap.isNotEmpty()) {                    
			val index = heap.poll()
			executedList.add(index)
			count[index]--
		}
		// NOTE: We don't do this during above iteration, it affects
		// the order of the heap during `heap.poll()`!!	
		// We need to poll() the heap in n + 1 times first, then
		// add back the executed tasks.
		for (index in executedList) {
			if (count[index] > 0) heap.add(index)
		}

		intervals += executedList.size

		// Insert the idle interval at the end but not the last interval
		// [A, B, C, D] ... [A, B, _, _] [A]	
		//                         ^^^^      XXXX
		// 					       idle      no idle when there is no other tasks
		// +1 means moving to "the next index" we can start for the next iteration
		// [A, B, _, _] [A, ...]
		//     i         i
		//     i + (2+1)
		if (heap.isNotEmpty()) intervals += (n - executedList.size) + 1
	}
	return intervals
}

Greedy (Counting)

We can split the timeline by intervals, and use the most frequent task to determine how many intervals we need.

// A, A, A, B, B, C
// maximum frequency = 3, interval = 3
A, _, _, _
A, _, _, _
A, ...

// A, A, A, B, B, B, C
// maximum frequency = 3, interval = 3
A, B, C
A, B, _
A, B, _

Suppose we have maxFreq as the maximum frequency of the tasks, and maxCount as the number of tasks that have the same maximum frequency. We can split the timeline into maxFreq - 1 parts, and each part has n - (maxCount - 1) empty slots.

A, _, _, _  // -----------
A, _, _, _  // maxFreq - 1
A, _, _, _  // -----------
|~ n + 1 ~|

A, ... // Last layer (see below)

Then we fill the most frequent tasks at the last layer, which is maxCount. Total is (maxFreq - 1) * (n - (maxCount - 1)) + maxCount. We also need to compare with the total number of tasks for the case that most frequent tasks is more than interval n, so the final result is the maximum of the above calculation and the total number of tasks.

fun leastInterval(tasks: CharArray, n: Int): Int {
	val count = IntArray(26)
	var maxFreq = 0
	for (c in tasks) {
		count[c - 'A']++
		maxFreq = maxOf(maxFreq, count[c - 'A'])
	}   
	var maxCount = 0    
	for (c in count) {
		if (c == maxFreq) maxCount++
	}
	return maxOf(tasks.size, (maxFreq - 1) * (n + 1) + maxCount)
}

Time Complexity: O(n).
Space Complexity: O(1).

FilesExpand file tree

621.task-scheduler.md

Latest commit

History