621.task-scheduler.md

621. Task Scheduler

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)

TODO: Understand the greedy solution.

Nice explanation: https://leetcode.com/problems/task-scheduler/solutions/104500/java-o-n-time-o-1-space-1-pass-no-sorting-solution-with-detailed-explanation/

// Input
[A, A, A, B, B, C] n = 2

// Count Map
A: 3
B: 2
C: 1

// Schedule
A x x A x x A
  B     B C

// If there are multiple most frequency tasks
A: 3
B: 3
C: 1

A B x x A B x x A B
// Group A, B together, it becomes
[A B] x x [A B] x x [A B]
// Becomes
  O   x x   O   x x   O

// Compare to before
A x x x A x x x A
O x x   O x x   O  

// availableTasks = tasks.length - count(A) * most freq tasks count
// partCount = count(A) - 1, most freq count - 1
// emptySlots = partCount * (n - (most freq tasks count - 1))
// idles = max(0, emptySlots - availableTasks)

fun leastInterval(tasks: CharArray, n: Int): Int {
    val counts = IntArray(26)
    var max = 0
    // Count how many task have same most frequency
    var maxCount = 0
    for (task in tasks) {
        counts[task - 'A']++
        val count = counts[task - 'A']
        if (max < count) {
            max = count
            maxCount = 1
        } else if (max == count) {
            maxCount++
        }
    }

    val partCounts = max - 1
    val emptySlots = partCounts * (n - (maxCount - 1))
    val availableTasks = tasks.size - max * maxCount
    val idles = max(0, emptySlots - availableTasks)
    return tasks.size + idles
}

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