Task Scheduler (CPU Cooling)

🎯

Task Scheduler (CPU Cooling)

mediumGREEDYFacebookAmazonGoogle

Imagine a CPU that must execute a list of tasks, but it needs to cool down between identical tasks to avoid overheating. How do you schedule tasks to minimize total execution time?

💡 This problem is about scheduling tasks with constraints on cooldown periods. Beginners often struggle because it looks like a complex scheduling problem, but a greedy approach based on task frequencies and idle time calculation simplifies it.

📋

Problem Statement

Given a list of tasks represented by capital letters A to Z, and a non-negative integer n representing the cooldown period between two identical tasks, return the least number of units of times the CPU will take to finish all the tasks. The CPU can either execute a task or stay idle during a unit of time. Tasks can be executed in any order.

1 ≤ tasks.length ≤ 10^5tasks[i] is an uppercase English letter.0 ≤ n ≤ 100

💡

Example

Input"tasks = ['A','A','A','B','B','B'], n = 2"

Output8

One possible schedule is A -> B -> idle -> A -> B -> idle -> A -> B. Total time is 8.

• All tasks are the same and n > 0 → output is (tasks.length - 1) * (n + 1) + 1
• n = 0 (no cooldown) → output is tasks.length
• Tasks all unique → output is tasks.length
• Large n with few tasks → output includes many idle slots

⚠️

Common Mistakes

Miscounting idle slots by not considering multiple tasks with max frequency

Returns incorrect minimum time, often too small

✅ Count how many tasks have max frequency and adjust formula accordingly

Assuming no idle time needed when n=0 without verifying task order

May overcomplicate or undercount time

✅ Return tasks.length directly when n=0

Using brute force simulation for large inputs

Code times out or runs too slowly

✅ Use greedy formula or max-heap approach for efficiency

Not updating frequencies correctly after task execution

Infinite loops or incorrect scheduling

✅ Decrease frequency and remove task when frequency hits zero

Incorrectly calculating part_length as n instead of n - (max_count - 1)

Idle time overestimated, leading to wrong answer

✅ Adjust part_length to account for multiple max frequency tasks

🧠

Brute Force (Simulation with Idle Insertion)

💡 This approach tries to simulate the scheduling by repeatedly picking the next available task and inserting idle times when necessary. It is intuitive but inefficient for large inputs.

Intuition

At each time unit, pick a task that can be executed (not in cooldown). If none is available, insert idle time. Repeat until all tasks are done.

Algorithm

1. Count the frequency of each task.
2. Maintain a cooldown queue to track tasks in cooldown.
3. At each time unit, pick the highest frequency task not in cooldown.
4. If no task is available, CPU idles.
5. Update frequencies and cooldown queue until all tasks are done.

💡 The challenge is managing cooldown and choosing tasks greedily each time, which is complex to implement and slow.

</>

Code

from collections import Counter, deque

def leastInterval(tasks, n):
    freq = Counter(tasks)
    time = 0
    cooldown = deque()  # stores pairs (task, ready_time)
    while freq or cooldown:
        time += 1
        # Release tasks from cooldown if ready_time <= current time
        while cooldown and cooldown[0][1] <= time:
            task = cooldown.popleft()[0]
            freq[task] = freq.get(task, 0) + 1
        if freq:
            # Pick task with highest frequency
            task = max(freq, key=freq.get)
            freq[task] -= 1
            if freq[task] == 0:
                del freq[task]
            cooldown.append((task, time + n + 1))
    return time

# Example usage
if __name__ == '__main__':
    print(leastInterval(['A','A','A','B','B','B'], 2))  # Output: 8

Line Notes

freq = Counter(tasks)Count how many times each task appears to know frequencies.

time = 0Initialize the time counter to track total units.

cooldown = deque()Use a queue to track tasks currently cooling down with their ready times.

while freq or cooldown:Continue until all tasks are done and no tasks are cooling down.

time += 1Increment time at each iteration representing one unit of CPU time.

while cooldown and cooldown[0][1] <= time:Release all tasks whose cooldown has expired and are ready to be scheduled again.

task = cooldown.popleft()[0]Remove the task from cooldown and add it back to frequency map.

task = max(freq, key=freq.get)Pick the task with the highest remaining frequency to execute next.

freq[task] -= 1Decrease the frequency of the executed task.

if freq[task] == 0: del freq[task]Remove the task from frequency map if completed.

cooldown.append((task, time + n + 1))Add the executed task to cooldown with its next available time.

import java.util.*;

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char t : tasks) freq.put(t, freq.getOrDefault(t, 0) + 1);
        Queue<Map.Entry<Character, Integer>> cooldown = new LinkedList<>();
        int time = 0;
        while (!freq.isEmpty() || !cooldown.isEmpty()) {
            time++;
            // Release tasks from cooldown if ready_time <= current time
            while (!cooldown.isEmpty() && cooldown.peek().getValue() <= time) {
                char task = cooldown.poll().getKey();
                freq.put(task, freq.getOrDefault(task, 0) + 1);
            }
            if (!freq.isEmpty()) {
                char task = Collections.max(freq.entrySet(), Map.Entry.comparingByValue()).getKey();
                freq.put(task, freq.get(task) - 1);
                if (freq.get(task) == 0) freq.remove(task);
                cooldown.offer(new AbstractMap.SimpleEntry<>(task, time + n + 1));
            }
        }
        return time;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.leastInterval(new char[]{'A','A','A','B','B','B'}, 2)); // 8
    }
}

Line Notes

Map<Character, Integer> freq = new HashMap<>()Count frequencies of each task.

Queue<Map.Entry<Character, Integer>> cooldown = new LinkedList<>()Track tasks in cooldown with their ready times.

while (!freq.isEmpty() || !cooldown.isEmpty())Loop until all tasks are done and cooldown is empty.

time++Increment time unit by unit.

while (!cooldown.isEmpty() && cooldown.peek().getValue() <= time)Release all tasks whose cooldown has expired and are ready to be scheduled again.

char task = cooldown.poll().getKey()Retrieve task ready to be scheduled again.

char task = Collections.max(freq.entrySet(), Map.Entry.comparingByValue()).getKey()Pick task with highest frequency to execute.

freq.put(task, freq.get(task) - 1)Decrease frequency after execution.

if (freq.get(task) == 0) freq.remove(task)Remove task if completed.

cooldown.offer(new AbstractMap.SimpleEntry<>(task, time + n + 1))Add task to cooldown with next available time.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

using namespace std;

int leastInterval(vector<char>& tasks, int n) {
    unordered_map<char, int> freq;
    for (char t : tasks) freq[t]++;
    queue<pair<char,int>> cooldown;
    int time = 0;
    while (!freq.empty() || !cooldown.empty()) {
        time++;
        // Release tasks from cooldown if ready_time <= current time
        while (!cooldown.empty() && cooldown.front().second <= time) {
            char task = cooldown.front().first;
            cooldown.pop();
            freq[task]++;
        }
        if (!freq.empty()) {
            auto it = max_element(freq.begin(), freq.end(), [](auto &a, auto &b){ return a.second < b.second; });
            char task = it->first;
            freq[task]--;
            if (freq[task] == 0) freq.erase(task);
            cooldown.push({task, time + n + 1});
        }
    }
    return time;
}

int main() {
    vector<char> tasks = {'A','A','A','B','B','B'};
    int n = 2;
    cout << leastInterval(tasks, n) << endl; // 8
    return 0;
}

Line Notes

unordered_map<char, int> freq;Count frequency of each task.

queue<pair<char,int>> cooldown;Track tasks in cooldown with their ready times.

while (!freq.empty() || !cooldown.empty())Loop until all tasks are done and cooldown is empty.

time++;Increment time unit by unit.

while (!cooldown.empty() && cooldown.front().second <= time)Release all tasks whose cooldown has expired and are ready to be scheduled again.

char task = cooldown.front().first; cooldown.pop();Retrieve task ready to be scheduled again.

auto it = max_element(freq.begin(), freq.end(), ...);Find task with highest frequency to execute.

freq[task]--; if (freq[task] == 0) freq.erase(task);Decrease frequency and remove if done.

cooldown.push({task, time + n + 1});Add task to cooldown with next available time.

function leastInterval(tasks, n) {
    const freq = new Map();
    for (const t of tasks) freq.set(t, (freq.get(t) || 0) + 1);
    const cooldown = [];
    let time = 0;
    while (freq.size > 0 || cooldown.length > 0) {
        time++;
        // Release tasks from cooldown if ready_time <= current time
        while (cooldown.length > 0 && cooldown[0][1] <= time) {
            const [task] = cooldown.shift();
            freq.set(task, (freq.get(task) || 0) + 1);
        }
        if (freq.size > 0) {
            let maxTask = null, maxCount = -1;
            for (const [task, count] of freq.entries()) {
                if (count > maxCount) {
                    maxCount = count;
                    maxTask = task;
                }
            }
            freq.set(maxTask, maxCount - 1);
            if (freq.get(maxTask) === 0) freq.delete(maxTask);
            cooldown.push([maxTask, time + n + 1]);
        }
    }
    return time;
}

// Example usage
console.log(leastInterval(['A','A','A','B','B','B'], 2)); // 8

Line Notes

const freq = new Map();Count frequency of each task.

const cooldown = [];Array to track tasks in cooldown with ready times.

while (freq.size > 0 || cooldown.length > 0)Loop until all tasks are done and cooldown is empty.

time++;Increment time unit by unit.

while (cooldown.length > 0 && cooldown[0][1] <= time)Release all tasks whose cooldown has expired and are ready to be scheduled again.

const [task] = cooldown.shift();Retrieve task ready to be scheduled again.

for (const [task, count] of freq.entries())Find task with highest frequency to execute.

freq.set(maxTask, maxCount - 1);Decrease frequency after execution.

if (freq.get(maxTask) === 0) freq.delete(maxTask);Remove task if completed.

cooldown.push([maxTask, time + n + 1]);Add task to cooldown with next available time.

⏱

Complexity

TimeO(m * t) where m is number of unique tasks and t is total time units

SpaceO(m + n) for frequency map and cooldown queue

At each time unit, we scan frequencies to pick max task, which is costly for large inputs.

💡 For 100 tasks and 2 cooldown, this approach might do thousands of operations, which is inefficient.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large inputs but helps understand the problem and constraints.

🧠

Greedy with Frequency Sorting and Idle Time Calculation

💡 This approach uses the insight that the task with the highest frequency determines the minimum schedule length. It avoids simulation by calculating idle slots needed.

Intuition

Arrange the most frequent tasks first with cooldown gaps, then fill idle slots with other tasks or reduce idle if enough tasks exist.

Algorithm

1. Count frequencies of all tasks.
2. Find the maximum frequency max_freq.
3. Count how many tasks have this max frequency (max_count).
4. Calculate minimum intervals using formula: (max_freq - 1) * (n + 1) + max_count.
5. Return the maximum of this value and total number of tasks.

💡 The formula accounts for the most frequent tasks and cooldown, ensuring no invalid idle time is counted.

</>

Code

from collections import Counter

def leastInterval(tasks, n):
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for v in freq.values() if v == max_freq)
    part_count = max_freq - 1
    part_length = n - (max_count - 1)
    empty_slots = part_count * part_length
    available_tasks = len(tasks) - max_freq * max_count
    idles = max(0, empty_slots - available_tasks)
    return len(tasks) + idles

# Example usage
if __name__ == '__main__':
    print(leastInterval(['A','A','A','B','B','B'], 2))  # Output: 8

Line Notes

freq = Counter(tasks)Count frequency of each task.

max_freq = max(freq.values())Find the highest frequency among tasks.

max_count = sum(1 for v in freq.values() if v == max_freq)Count how many tasks have this max frequency.

part_count = max_freq - 1Number of full parts between the most frequent tasks.

part_length = n - (max_count - 1)Length of each part excluding slots taken by max frequency tasks.

empty_slots = part_count * part_lengthTotal idle slots needed between max frequency tasks.

available_tasks = len(tasks) - max_freq * max_countTasks available to fill idle slots.

idles = max(0, empty_slots - available_tasks)Calculate actual idle slots after filling with other tasks.

return len(tasks) + idlesTotal time is tasks plus idle slots.

import java.util.*;

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char t : tasks) freq.put(t, freq.getOrDefault(t, 0) + 1);
        int max_freq = Collections.max(freq.values());
        int max_count = 0;
        for (int v : freq.values()) if (v == max_freq) max_count++;
        int part_count = max_freq - 1;
        int part_length = n - (max_count - 1);
        int empty_slots = part_count * part_length;
        int available_tasks = tasks.length - max_freq * max_count;
        int idles = Math.max(0, empty_slots - available_tasks);
        return tasks.length + idles;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.leastInterval(new char[]{'A','A','A','B','B','B'}, 2)); // 8
    }
}

Line Notes

Map<Character, Integer> freq = new HashMap<>()Count frequency of each task.

int max_freq = Collections.max(freq.values())Find the highest frequency.

for (int v : freq.values()) if (v == max_freq) max_count++Count tasks with max frequency.

int part_count = max_freq - 1Number of parts between max frequency tasks.

int part_length = n - (max_count - 1)Length of each part excluding max frequency tasks.

int empty_slots = part_count * part_lengthCalculate idle slots needed.

int available_tasks = tasks.length - max_freq * max_countTasks available to fill idle slots.

int idles = Math.max(0, empty_slots - available_tasks)Calculate actual idle slots after filling.

return tasks.length + idlesTotal time is tasks plus idle slots.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int leastInterval(vector<char>& tasks, int n) {
    unordered_map<char, int> freq;
    for (char t : tasks) freq[t]++;
    int max_freq = 0;
    for (auto& p : freq) max_freq = max(max_freq, p.second);
    int max_count = 0;
    for (auto& p : freq) if (p.second == max_freq) max_count++;
    int part_count = max_freq - 1;
    int part_length = n - (max_count - 1);
    int empty_slots = part_count * part_length;
    int available_tasks = (int)tasks.size() - max_freq * max_count;
    int idles = max(0, empty_slots - available_tasks);
    return (int)tasks.size() + idles;
}

int main() {
    vector<char> tasks = {'A','A','A','B','B','B'};
    int n = 2;
    cout << leastInterval(tasks, n) << endl; // 8
    return 0;
}

Line Notes

unordered_map<char, int> freq;Count frequency of each task.

int max_freq = 0; for (auto& p : freq) max_freq = max(max_freq, p.second);Find max frequency.

int max_count = 0; for (auto& p : freq) if (p.second == max_freq) max_count++;Count tasks with max frequency.

int part_count = max_freq - 1;Number of parts between max frequency tasks.

int part_length = n - (max_count - 1);Length of each part excluding max frequency tasks.

int empty_slots = part_count * part_length;Calculate idle slots needed.

int available_tasks = (int)tasks.size() - max_freq * max_count;Tasks available to fill idle slots.

int idles = max(0, empty_slots - available_tasks);Calculate actual idle slots after filling.

return (int)tasks.size() + idles;Total time is tasks plus idle slots.

function leastInterval(tasks, n) {
    const freq = new Map();
    for (const t of tasks) freq.set(t, (freq.get(t) || 0) + 1);
    let max_freq = 0;
    for (const v of freq.values()) max_freq = Math.max(max_freq, v);
    let max_count = 0;
    for (const v of freq.values()) if (v === max_freq) max_count++;
    const part_count = max_freq - 1;
    const part_length = n - (max_count - 1);
    const empty_slots = part_count * part_length;
    const available_tasks = tasks.length - max_freq * max_count;
    const idles = Math.max(0, empty_slots - available_tasks);
    return tasks.length + idles;
}

// Example usage
console.log(leastInterval(['A','A','A','B','B','B'], 2)); // 8

Line Notes

const freq = new Map();Count frequency of each task.

let max_freq = 0; for (const v of freq.values()) max_freq = Math.max(max_freq, v);Find max frequency.

let max_count = 0; for (const v of freq.values()) if (v === max_freq) max_count++;Count tasks with max frequency.

const part_count = max_freq - 1;Number of parts between max frequency tasks.

const part_length = n - (max_count - 1);Length of each part excluding max frequency tasks.

const empty_slots = part_count * part_length;Calculate idle slots needed.

const available_tasks = tasks.length - max_freq * max_count;Tasks available to fill idle slots.

const idles = Math.max(0, empty_slots - available_tasks);Calculate actual idle slots after filling.

return tasks.length + idles;Total time is tasks plus idle slots.

⏱

Complexity

TimeO(m) where m is number of unique tasks

SpaceO(m) for frequency map

We only count frequencies and do constant time calculations, no simulation.

💡 For 26 tasks, this approach is very fast and scalable.

Interview Verdict: Accepted / Optimal for large inputs

This approach is efficient and the preferred solution in interviews.

🧠

Greedy with Max-Heap Priority Queue

💡 This approach uses a max-heap to always pick the task with the highest remaining frequency, simulating the scheduling but more efficiently than brute force.

Intuition

Use a max-heap to pick the most frequent task available, execute it, then put it in cooldown. Repeat until all tasks are done.

Algorithm

1. Count frequencies of tasks.
2. Add all tasks to a max-heap based on frequency.
3. At each cycle of n+1 units, pick tasks from heap to execute.
4. Decrease frequency and add back to heap if still remaining.
5. Count total time including idle if less than n+1 tasks executed.

💡 This simulates the CPU scheduling in chunks, ensuring cooldown is respected without explicit cooldown tracking.

</>

Code

from collections import Counter
import heapq

def leastInterval(tasks, n):
    freq = Counter(tasks)
    max_heap = [-cnt for cnt in freq.values()]
    heapq.heapify(max_heap)
    time = 0
    while max_heap:
        temp = []
        cycle = 0
        for _ in range(n + 1):
            if max_heap:
                cnt = heapq.heappop(max_heap)
                if cnt + 1 < 0:
                    temp.append(cnt + 1)
                cycle += 1
            else:
                break
        for item in temp:
            heapq.heappush(max_heap, item)
        time += cycle if not max_heap else n + 1
    return time

# Example usage
if __name__ == '__main__':
    print(leastInterval(['A','A','A','B','B','B'], 2))  # Output: 8

Line Notes

freq = Counter(tasks)Count frequency of each task.

max_heap = [-cnt for cnt in freq.values()]Create max heap by negating counts.

heapq.heapify(max_heap)Heapify the list to form a max heap.

while max_heap:Loop until all tasks are scheduled.

temp = []Temporary list to hold tasks for next round.

for _ in range(n + 1):Try to execute up to n+1 tasks in one cycle.

cnt = heapq.heappop(max_heap)Pop the most frequent task.

if cnt + 1 < 0: temp.append(cnt + 1)Decrease frequency and add back if tasks remain.

time += cycle if not max_heap else n + 1Add time: full cycle if tasks remain, else partial.

import java.util.*;

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char t : tasks) freq.put(t, freq.getOrDefault(t, 0) + 1);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.addAll(freq.values());
        int time = 0;
        while (!maxHeap.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int cycle = 0;
            for (int i = 0; i <= n; i++) {
                if (!maxHeap.isEmpty()) {
                    int cnt = maxHeap.poll();
                    if (cnt > 1) temp.add(cnt - 1);
                    cycle++;
                } else break;
            }
            maxHeap.addAll(temp);
            time += maxHeap.isEmpty() ? cycle : n + 1;
        }
        return time;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.leastInterval(new char[]{'A','A','A','B','B','B'}, 2)); // 8
    }
}

Line Notes

Map<Character, Integer> freq = new HashMap<>()Count frequency of each task.

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder())Max heap to pick highest frequency task.

maxHeap.addAll(freq.values())Add all frequencies to heap.

while (!maxHeap.isEmpty())Loop until all tasks are scheduled.

List<Integer> temp = new ArrayList<>()Temporary list for tasks to re-add.

for (int i = 0; i <= n; i++)Try to execute up to n+1 tasks per cycle.

int cnt = maxHeap.poll()Pop most frequent task.

if (cnt > 1) temp.add(cnt - 1)Decrease frequency and add back if tasks remain.

time += maxHeap.isEmpty() ? cycle : n + 1Add time: full cycle or partial if done.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

int leastInterval(vector<char>& tasks, int n) {
    unordered_map<char, int> freq;
    for (char t : tasks) freq[t]++;
    priority_queue<int> maxHeap;
    for (auto& p : freq) maxHeap.push(p.second);
    int time = 0;
    while (!maxHeap.empty()) {
        vector<int> temp;
        int cycle = 0;
        for (int i = 0; i <= n; i++) {
            if (!maxHeap.empty()) {
                int cnt = maxHeap.top(); maxHeap.pop();
                if (cnt > 1) temp.push_back(cnt - 1);
                cycle++;
            } else break;
        }
        for (int cnt : temp) maxHeap.push(cnt);
        time += maxHeap.empty() ? cycle : n + 1;
    }
    return time;
}

int main() {
    vector<char> tasks = {'A','A','A','B','B','B'};
    int n = 2;
    cout << leastInterval(tasks, n) << endl; // 8
    return 0;
}

Line Notes

unordered_map<char, int> freq;Count frequency of each task.

priority_queue<int> maxHeap;Max heap to pick highest frequency task.

for (auto& p : freq) maxHeap.push(p.second);Add frequencies to heap.

while (!maxHeap.empty())Loop until all tasks scheduled.

vector<int> temp;Temporary vector for tasks to re-add.

for (int i = 0; i <= n; i++)Try to execute up to n+1 tasks per cycle.

int cnt = maxHeap.top(); maxHeap.pop();Pop most frequent task.

if (cnt > 1) temp.push_back(cnt - 1);Decrease frequency and add back if tasks remain.

time += maxHeap.empty() ? cycle : n + 1;Add time: full cycle or partial if done.

function leastInterval(tasks, n) {
    const freq = new Map();
    for (const t of tasks) freq.set(t, (freq.get(t) || 0) + 1);
    const maxHeap = [];
    for (const v of freq.values()) maxHeap.push(-v);
    maxHeap.sort();
    let time = 0;
    while (maxHeap.length > 0) {
        const temp = [];
        let cycle = 0;
        for (let i = 0; i <= n; i++) {
            if (maxHeap.length > 0) {
                let cnt = -maxHeap.shift();
                if (cnt > 1) temp.push(-(cnt - 1));
                cycle++;
            } else break;
        }
        maxHeap.push(...temp);
        maxHeap.sort();
        time += maxHeap.length === 0 ? cycle : n + 1;
    }
    return time;
}

// Example usage
console.log(leastInterval(['A','A','A','B','B','B'], 2)); // 8

Line Notes

const freq = new Map();Count frequency of each task.

const maxHeap = []; for (const v of freq.values()) maxHeap.push(-v);Simulate max heap by negating values.

maxHeap.sort();Sort to maintain heap property (inefficient but illustrative).

while (maxHeap.length > 0)Loop until all tasks scheduled.

const temp = [];Temporary array for tasks to re-add.

for (let i = 0; i <= n; i++)Try to execute up to n+1 tasks per cycle.

let cnt = -maxHeap.shift();Pop most frequent task.

if (cnt > 1) temp.push(-(cnt - 1));Decrease frequency and add back if tasks remain.

time += maxHeap.length === 0 ? cycle : n + 1;Add time: full cycle or partial if done.

⏱

Complexity

TimeO(t log m) where t is total tasks and m is unique tasks

SpaceO(m) for frequency map and heap

Each task is pushed and popped from heap at most once per execution.

💡 For 100 tasks and 26 unique, this approach is efficient and simulates scheduling well.

Interview Verdict: Accepted / Efficient simulation

This approach balances clarity and efficiency, good for interviews if you want to simulate scheduling.

📊

All Approaches - One-Glance Tradeoffs

💡 The greedy formula approach is the best to code in 95% of interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Simulation with Idle Insertion)	O(m * t) where m is unique tasks, t is total time units	O(m + n)	No	N/A	Mention only - never code due to inefficiency
2. Greedy with Frequency Sorting and Idle Time Calculation	O(m)	O(m)	No	N/A	Code this approach for optimal solution
3. Greedy with Max-Heap Priority Queue	O(t log m)	O(m)	No	N/A	Good alternative to simulate scheduling if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and know when to use each. Read before every mock interview to build confidence.

How to Present

Step 1: Clarify the problem and constraints, especially the cooldown period.Step 2: Describe the brute force simulation approach to show understanding.Step 3: Explain the greedy formula approach for optimal solution.Step 4: Optionally discuss the max-heap simulation for clarity.Step 5: Code the greedy formula approach for efficiency.Step 6: Test with edge cases and explain reasoning.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of greedy scheduling, ability to optimize from brute force, and correctness of idle time calculation.

Common Follow-ups

• What if tasks have different execution times? → Modify approach to account for varying durations.
• How to handle multiple CPUs? → Extend scheduling logic to parallel execution.

💡 These follow-ups test your ability to adapt the solution to more complex real-world scenarios.

🔍

Pattern Recognition

When to Use

1) Tasks with cooldown or waiting period, 2) Need to minimize total time or idle, 3) Tasks can be reordered, 4) Frequency of tasks matters

Signature Phrases

cooldown period between same tasksminimum intervals to finish tasks

NOT This Pattern When

Problems requiring DP for subsequence or substring optimization, or strict ordering constraints

Similar Problems

Rearrange String k Distance Apart - similar cooldown and rearrangement constraintsMinimum Number of Intervals to Remove - related to interval scheduling optimization

Practice

1. Consider the following buggy code for candy distribution. Which line contains the subtle bug that can cause incorrect candy counts?

medium

A. Line 3: candies initialized with zeros instead of ones

B. Line 5: loop starts from 1 instead of 0

C. Line 7: candies[i] updated without checking if greater than candies[i-1]

D. Line 9: condition candies[i] <= candies[i + 1] missing

Solution

1. Step 1: Check initialization of candies array

   Line 3 initializes candies with zeros, violating the problem requirement that each child must have at least one candy.

2. Step 2: Understand impact of zero initialization

   Zero candies can cause incorrect comparisons and final sums, failing test cases where minimum is 1 per child.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initialization must be at least 1 per child [OK]

Hint: Candies must start at 1, not 0 [OK]

Common Mistakes:

• Forgetting minimum candy per child
• Incorrect loop boundaries
• Missing update conditions

2. The following code attempts to solve the Jump Game problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        # Bug: missing check if current index is beyond maxReach
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

medium

A. Line 2: Initialization of maxReach

B. Line 3: for loop header enumerating nums

C. Line 4: Missing check if i > maxReach before updating maxReach

D. Line 6: Checking if maxReach reaches or exceeds last index

Solution

1. Step 1: Understand the missing condition

   The code does not check if the current index i is beyond maxReach, which means it may continue even when stuck.

2. Step 2: Identify the bug line

   Line 4 updates maxReach without verifying if i is reachable, causing false positives on inputs with unreachable indices.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding "if i > maxReach: return False" fixes the bug [OK]

Hint: Check if current index is reachable before updating maxReach [OK]

Common Mistakes:

• Forgetting to check i > maxReach
• Assuming maxReach update alone suffices

3. What is the time complexity of the optimal greedy solution for the Maximum Units on a Truck problem, assuming n is the number of box types and truckSize is the truck capacity?

medium

A. O(n log n)

B. O(n)

C. O(n * truckSize)

D. O(truckSize log n)

Solution

1. Step 1: Identify main operations

   The algorithm sorts boxTypes by units per box descending, which takes O(n log n).

2. Step 2: Analyze iteration cost

   After sorting, it iterates over boxTypes once, O(n), picking boxes until truckSize is exhausted.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, so total complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity [OK]

Common Mistakes:

• Confusing truckSize as multiplicative factor
• Assuming O(n * truckSize) due to iteration
• Ignoring sorting cost

4. Suppose now each cookie can be assigned to multiple children (reusable cookies). Which modification to the original greedy algorithm correctly computes the maximum number of content children?

hard

A. Sort both arrays and increment both pointers i and j on assignment as before

B. Use the brute force nested loops approach to try all assignments since greedy fails with reusable cookies

C. Sort greed array only and assign the largest cookie to each child without sorting cookies

D. Keep sorting arrays, but do not increment cookie pointer j when a cookie is assigned; only increment child pointer i

Solution

1. Step 1: Understand reuse effect

   Cookies can be assigned multiple times, so cookie pointer j should not advance on assignment.

2. Step 2: Modify greedy accordingly

   Keep sorting both arrays, but only increment child pointer i when a cookie satisfies a child; j stays to reuse the same cookie.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Not incrementing j allows cookie reuse [OK]

Hint: Do not advance cookie pointer on assignment for reuse [OK]

Common Mistakes:

• Incrementing both pointers breaks reuse
• Using brute force unnecessarily
• Ignoring sorting leads to suboptimal matches

5. Suppose trains can arrive and depart multiple times (reusing platforms), or the station allows fractional arrival/departure times. Which modification to the min-heap approach correctly handles these cases?

hard

A. Use brute force nested loops to check all overlaps since fractional times break heap ordering

B. Sort arrivals and departures separately and use two pointers to count overlaps

C. Keep the min-heap but change the comparison to strictly less than (<) to handle fractional times

D. Use a balanced BST instead of a min-heap to handle fractional times and reuse efficiently

Solution

1. Step 1: Identify challenges with fractional and multiple reuse

   Fractional times and multiple reuse require precise ordering and efficient insertion/removal of intervals.

2. Step 2: Choose data structure

   A balanced BST supports ordered insertions, deletions, and queries with fractional keys better than a min-heap, which assumes discrete ordering.

3. Step 3: Why other options fail

   Two pointers fail with fractional times due to equality checks; changing comparison in heap breaks correctness; brute force is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Balanced BST handles fractional and reuse efficiently [OK]

Hint: Balanced BST supports fractional keys and dynamic reuse [OK]

Common Mistakes:

• Assuming min-heap works unchanged with fractional times
• Using two pointers without handling fractional equality
• Resorting to brute force for efficiency