Task Scheduler II (Cooldown Tracking)

🎯

Task Scheduler II (Cooldown Tracking)

mediumHEAPAmazonGoogle

Imagine you are managing a factory line where each task requires a cooldown period before it can be executed again. You want to schedule tasks as soon as possible without violating cooldown constraints.

💡 This problem involves scheduling tasks with cooldowns, which can be tricky because you must track when each task becomes available again. Beginners often struggle to efficiently track cooldowns and decide the earliest time to schedule the next task.

📋

Problem Statement

Given an array tasks where tasks[i] represents the type of the ith task, and an integer space representing the cooldown period, schedule the tasks in order such that the same task type is executed at least space units apart. Return the earliest day number (1-indexed) when all tasks can be completed. Each day you can execute exactly one task or be idle.

1 ≤ tasks.length ≤ 10^51 ≤ tasks[i] ≤ 10^90 ≤ space ≤ 10^9

💡

Example

Input"tasks = [1,2,1,2,3,1], space = 3"

Output9

Schedule tasks as: day 1: task 1, day 2: task 2, day 3: idle, day 4: idle, day 5: task 1, day 6: task 2, day 7: task 3, day 8: idle, day 9: task 1.

• All tasks are unique → output is tasks.length
• space = 0 → tasks can be scheduled consecutively without delay
• All tasks are the same → output is (tasks.length - 1) * (space + 1) + 1
• Very large space with few tasks → output is tasks.length + space * (tasks.length - 1)

⚠️

Common Mistakes

Not updating the current day correctly when cooldown is violated

Tasks get scheduled too early, violating cooldown constraints

✅ Always update current day to max(current day, earliest next available day for the task)

Simulating idle days explicitly leading to TLE

Code runs too slowly for large inputs

✅ Use a hash map to jump days forward instead of simulating each idle day

Using a data structure that doesn't support O(1) lookups for last execution day

Increased time complexity, possibly TLE

✅ Use a hash map or dictionary for constant time lookups

Confusing 0-based and 1-based day counting

Off-by-one errors in final answer

✅ Start counting days from 1 as per problem statement

Not handling the case when space = 0 correctly

Unnecessary day jumps or idle days

✅ When space = 0, tasks can be scheduled consecutively without delay

🧠

Brute Force (Simulate Day by Day)

💡 This approach exists to build intuition by simulating the scheduling process day by day, which helps understand the cooldown constraints but is inefficient for large inputs.

Intuition

Try to schedule each task on the earliest possible day by checking if the cooldown period has passed since the last execution of the same task. If not, wait (idle) until it is allowed.

Algorithm

1. Initialize current day to 1.
2. For each task in order, check the last day it was executed.
3. If the cooldown period has not passed, increment current day until cooldown is satisfied.
4. Schedule the task on the current day and update the last executed day for that task.

💡 This approach is straightforward but requires careful tracking of last execution days and waiting, which can be slow if implemented naively.

</>

Code

def task_scheduler_brute(tasks, space):
    last_day = {}
    day = 1
    for t in tasks:
        if t in last_day and day - last_day[t] <= space:
            day = last_day[t] + space + 1
        last_day[t] = day
        day += 1
    return day - 1

# Driver code
if __name__ == '__main__':
    tasks = [1,2,1,2,3,1]
    space = 3
    print(task_scheduler_brute(tasks, space))  # Expected output: 9

Line Notes

last_day = {}Stores the last day each task was executed to enforce cooldown

day = 1Start counting days from 1 as per problem statement

if t in last_day and day - last_day[t] <= space:Check if cooldown period is violated for current task

day = last_day[t] + space + 1If cooldown violated, jump day forward to earliest allowed day

last_day[t] = dayUpdate last execution day for current task

day += 1Move to next day after scheduling current task

import java.util.*;
public class TaskSchedulerBrute {
    public static int taskScheduler(int[] tasks, int space) {
        Map<Integer, Integer> lastDay = new HashMap<>();
        int day = 1;
        for (int t : tasks) {
            if (lastDay.containsKey(t) && day - lastDay.get(t) <= space) {
                day = lastDay.get(t) + space + 1;
            }
            lastDay.put(t, day);
            day++;
        }
        return day - 1;
    }
    public static void main(String[] args) {
        int[] tasks = {1,2,1,2,3,1};
        int space = 3;
        System.out.println(taskScheduler(tasks, space)); // Expected: 9
    }
}

Line Notes

Map<Integer, Integer> lastDay = new HashMap<>();Tracks last execution day per task

int day = 1;Initialize day counter starting at 1

if (lastDay.containsKey(t) && day - lastDay.get(t) <= space)Check cooldown violation for current task

day = lastDay.get(t) + space + 1;Adjust day to earliest allowed day if cooldown violated

lastDay.put(t, day);Update last execution day for task

day++;Increment day after scheduling

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int taskSchedulerBrute(const vector<int>& tasks, int space) {
    unordered_map<int, int> lastDay;
    int day = 1;
    for (int t : tasks) {
        if (lastDay.count(t) && day - lastDay[t] <= space) {
            day = lastDay[t] + space + 1;
        }
        lastDay[t] = day;
        day++;
    }
    return day - 1;
}

int main() {
    vector<int> tasks = {1,2,1,2,3,1};
    int space = 3;
    cout << taskSchedulerBrute(tasks, space) << endl; // Expected: 9
    return 0;
}

Line Notes

unordered_map<int, int> lastDay;Stores last execution day for each task

int day = 1;Start counting days from 1

if (lastDay.count(t) && day - lastDay[t] <= space)Check if cooldown is violated for current task

day = lastDay[t] + space + 1;Jump day forward to satisfy cooldown

lastDay[t] = day;Update last execution day for task

day++;Increment day after scheduling

function taskSchedulerBrute(tasks, space) {
    const lastDay = new Map();
    let day = 1;
    for (const t of tasks) {
        if (lastDay.has(t) && day - lastDay.get(t) <= space) {
            day = lastDay.get(t) + space + 1;
        }
        lastDay.set(t, day);
        day++;
    }
    return day - 1;
}

// Test
const tasks = [1,2,1,2,3,1];
const space = 3;
console.log(taskSchedulerBrute(tasks, space)); // Expected: 9

Line Notes

const lastDay = new Map();Map to track last execution day per task

let day = 1;Initialize day counter starting at 1

if (lastDay.has(t) && day - lastDay.get(t) <= space)Check cooldown violation for current task

day = lastDay.get(t) + space + 1;Adjust day to earliest allowed day if cooldown violated

lastDay.set(t, day);Update last execution day for task

day++;Increment day after scheduling

⏱

Complexity

TimeO(n)

SpaceO(n)

We iterate through all tasks once, and each lookup/update in the map is O(1) on average. Space is O(n) to store last execution days.

💡 For n=100,000 tasks, this means about 100,000 operations, which is efficient enough for most cases.

Interview Verdict: Accepted

Though simple, this approach is efficient and accepted because it uses a hash map to track cooldowns without simulating idle days explicitly.

🧠

Using a Min-Heap to Track Next Available Days (Conceptual Explanation)

💡 This approach introduces the concept of a min-heap to efficiently track the earliest day a task can be scheduled, which is useful when tasks can be reordered or when we want to simulate scheduling with idle days explicitly. However, the provided code uses a hash map only for simplicity and efficiency.

Intuition

Use a min-heap to store tasks with their earliest available day. For each task, wait until its earliest available day, schedule it, then update its next available day and push back into the heap. The code simulates this logic without an explicit heap for efficiency.

Algorithm

1. Initialize a min-heap to store pairs of (next_available_day, task).
2. Initialize current day to 1.
3. For each task in order, pop from heap if the task is available before current day.
4. If the task is not available, move current day forward to the task's next available day.
5. Schedule the task on current day, update its next available day to current day + space + 1, and push back into the heap.
6. Return the last scheduled day.

💡 This algorithm explicitly tracks when tasks become available and schedules them as soon as possible, using the heap to efficiently find the earliest available task. The code uses a hash map to jump days forward instead of explicit heap operations for efficiency.

</>

Code

def task_scheduler_heap(tasks, space):
    last_day = {}
    day = 1
    for t in tasks:
        if t in last_day:
            earliest = last_day[t] + space + 1
            if day < earliest:
                day = earliest
        last_day[t] = day
        day += 1
    return day - 1

# Driver code
if __name__ == '__main__':
    tasks = [1,2,1,2,3,1]
    space = 3
    print(task_scheduler_heap(tasks, space))  # Expected output: 9

Line Notes

last_day = {}Tracks last execution day per task to enforce cooldown

day = 1Start day count at 1 as per problem statement

for t in tasks:Iterate over each task in order

if t in last_day:Check if task was executed before to enforce cooldown

earliest = last_day[t] + space + 1Calculate earliest day task can be scheduled again

if day < earliest:If current day is before earliest allowed, jump forward to earliest

last_day[t] = dayUpdate last execution day for task

day += 1Increment day after scheduling current task

return day - 1Return the last day when all tasks are completed

import java.util.*;
public class TaskSchedulerHeap {
    public static int taskScheduler(int[] tasks, int space) {
        Map<Integer, Integer> lastDay = new HashMap<>();
        int day = 1;
        for (int t : tasks) {
            if (lastDay.containsKey(t)) {
                int earliest = lastDay.get(t) + space + 1;
                if (day < earliest) {
                    day = earliest;
                }
            }
            lastDay.put(t, day);
            day++;
        }
        return day - 1;
    }
    public static void main(String[] args) {
        int[] tasks = {1,2,1,2,3,1};
        int space = 3;
        System.out.println(taskScheduler(tasks, space)); // Expected: 9
    }
}

Line Notes

Map<Integer, Integer> lastDay = new HashMap<>();Stores last execution day per task to enforce cooldown

int day = 1;Initialize day counter starting at 1

for (int t : tasks) {Iterate over each task in order

if (lastDay.containsKey(t)) {Check if task was executed before

int earliest = lastDay.get(t) + space + 1;Calculate earliest allowed day for task

if (day < earliest) { day = earliest; }Jump day forward if cooldown not satisfied

lastDay.put(t, day);Update last execution day for task

day++;Increment day after scheduling

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int taskSchedulerHeap(const vector<int>& tasks, int space) {
    unordered_map<int, int> lastDay;
    int day = 1;
    for (int t : tasks) {
        if (lastDay.count(t)) {
            int earliest = lastDay[t] + space + 1;
            if (day < earliest) {
                day = earliest;
            }
        }
        lastDay[t] = day;
        day++;
    }
    return day - 1;
}

int main() {
    vector<int> tasks = {1,2,1,2,3,1};
    int space = 3;
    cout << taskSchedulerHeap(tasks, space) << endl; // Expected: 9
    return 0;
}

Line Notes

unordered_map<int, int> lastDay;Tracks last execution day per task to enforce cooldown

int day = 1;Start day count at 1

for (int t : tasks) {Iterate over each task in order

if (lastDay.count(t)) {Check if task was executed before

int earliest = lastDay[t] + space + 1;Calculate earliest allowed day for task

if (day < earliest) { day = earliest; }Jump day forward if cooldown not satisfied

lastDay[t] = day;Update last execution day for task

day++;Increment day after scheduling

function taskSchedulerHeap(tasks, space) {
    const lastDay = new Map();
    let day = 1;
    for (const t of tasks) {
        if (lastDay.has(t)) {
            const earliest = lastDay.get(t) + space + 1;
            if (day < earliest) {
                day = earliest;
            }
        }
        lastDay.set(t, day);
        day++;
    }
    return day - 1;
}

// Test
const tasks = [1,2,1,2,3,1];
const space = 3;
console.log(taskSchedulerHeap(tasks, space)); // Expected: 9

Line Notes

const lastDay = new Map();Map to track last execution day per task to enforce cooldown

let day = 1;Initialize day counter starting at 1

for (const t of tasks) {Iterate over each task in order

if (lastDay.has(t)) {Check if task was executed before

const earliest = lastDay.get(t) + space + 1;Calculate earliest allowed day for task

if (day < earliest) { day = earliest; }Jump day forward if cooldown not satisfied

lastDay.set(t, day);Update last execution day for task

day++;Increment day after scheduling

⏱

Complexity

TimeO(n)

SpaceO(n)

Each task is processed once with O(1) map lookups and updates. No explicit heap operations are performed here, so complexity remains linear.

💡 This approach is similar to brute force but conceptually uses a heap to think about earliest availability, still efficient for large inputs.

Interview Verdict: Accepted

This approach is optimal and accepted, illustrating how to think about scheduling with earliest availability without explicit idle simulation.

🧠

Optimized Tracking with Hash Map Only (Greedy)

💡 This approach is the most optimal and clean, using a hash map to track the earliest day each task can be scheduled next, greedily scheduling tasks as soon as possible.

Intuition

For each task, schedule it on the maximum of the current day or the earliest day it can be scheduled (based on cooldown). Update the earliest next available day for that task accordingly.

Algorithm

1. Initialize a hash map to store the earliest next available day for each task.
2. Initialize current day to 1.
3. For each task, update current day to max(current day, earliest next available day for that task).
4. Schedule the task on current day.
5. Update the earliest next available day for the task to current day + space + 1.
6. Increment current day and continue until all tasks are scheduled.
7. Return the last scheduled day.

💡 This greedy approach avoids explicit idle simulation by jumping the current day forward to the earliest allowed day for each task.

</>

Code

def task_scheduler_optimized(tasks, space):
    next_available = {}
    day = 1
    for t in tasks:
        if t in next_available:
            day = max(day, next_available[t])
        next_available[t] = day + space + 1
        day += 1
    return day - 1

# Driver code
if __name__ == '__main__':
    tasks = [1,2,1,2,3,1]
    space = 3
    print(task_scheduler_optimized(tasks, space))  # Expected output: 9

Line Notes

next_available = {}Tracks earliest day each task can be scheduled next

day = 1Start day count at 1

for t in tasks:Iterate over each task in order

if t in next_available:Check if task has a cooldown constraint

day = max(day, next_available[t])Jump day forward if cooldown not satisfied

next_available[t] = day + space + 1Update next available day for task after scheduling

day += 1Increment day after scheduling

return day - 1Return the last day when all tasks are completed

import java.util.*;
public class TaskSchedulerOptimized {
    public static int taskScheduler(int[] tasks, int space) {
        Map<Integer, Integer> nextAvailable = new HashMap<>();
        int day = 1;
        for (int t : tasks) {
            if (nextAvailable.containsKey(t)) {
                day = Math.max(day, nextAvailable.get(t));
            }
            nextAvailable.put(t, day + space + 1);
            day++;
        }
        return day - 1;
    }
    public static void main(String[] args) {
        int[] tasks = {1,2,1,2,3,1};
        int space = 3;
        System.out.println(taskScheduler(tasks, space)); // Expected: 9
    }
}

Line Notes

Map<Integer, Integer> nextAvailable = new HashMap<>();Tracks earliest next available day per task

int day = 1;Initialize day counter starting at 1

for (int t : tasks) {Iterate over each task in order

if (nextAvailable.containsKey(t)) {Check if task has cooldown

day = Math.max(day, nextAvailable.get(t));Jump day forward if cooldown not satisfied

nextAvailable.put(t, day + space + 1);Update next available day after scheduling

day++;Increment day after scheduling

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int taskSchedulerOptimized(const vector<int>& tasks, int space) {
    unordered_map<int, int> nextAvailable;
    int day = 1;
    for (int t : tasks) {
        if (nextAvailable.count(t)) {
            day = max(day, nextAvailable[t]);
        }
        nextAvailable[t] = day + space + 1;
        day++;
    }
    return day - 1;
}

int main() {
    vector<int> tasks = {1,2,1,2,3,1};
    int space = 3;
    cout << taskSchedulerOptimized(tasks, space) << endl; // Expected: 9
    return 0;
}

Line Notes

unordered_map<int, int> nextAvailable;Tracks earliest next available day per task

int day = 1;Start day count at 1

for (int t : tasks) {Iterate over each task in order

if (nextAvailable.count(t)) {Check if task has cooldown

day = max(day, nextAvailable[t]);Jump day forward if cooldown not satisfied

nextAvailable[t] = day + space + 1;Update next available day after scheduling

day++;Increment day after scheduling

function taskSchedulerOptimized(tasks, space) {
    const nextAvailable = new Map();
    let day = 1;
    for (const t of tasks) {
        if (nextAvailable.has(t)) {
            day = Math.max(day, nextAvailable.get(t));
        }
        nextAvailable.set(t, day + space + 1);
        day++;
    }
    return day - 1;
}

// Test
const tasks = [1,2,1,2,3,1];
const space = 3;
console.log(taskSchedulerOptimized(tasks, space)); // Expected: 9

Line Notes

const nextAvailable = new Map();Map to track earliest next available day per task

let day = 1;Initialize day counter starting at 1

for (const t of tasks) {Iterate over each task in order

if (nextAvailable.has(t)) {Check if task has cooldown

day = Math.max(day, nextAvailable.get(t));Jump day forward if cooldown not satisfied

nextAvailable.set(t, day + space + 1);Update next available day after scheduling

day++;Increment day after scheduling

⏱

Complexity

TimeO(n)

SpaceO(n)

Each task is processed once with O(1) hash map operations, making it optimal for large inputs.

💡 For 100,000 tasks, this approach efficiently computes the schedule in linear time without simulating idle days explicitly.

Interview Verdict: Accepted

This is the best approach to implement in interviews due to its simplicity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 The optimal greedy approach is the best to implement in interviews due to its simplicity and efficiency. Brute force is useful for understanding, and heap-based approaches illustrate scheduling concepts.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	N/A	Mention only - never code
2. Min-Heap Tracking (Conceptual)	O(n)	O(n)	No	N/A	Explain conceptually, but code simpler approach
3. Optimized Greedy with Hash Map	O(n)	O(n)	No	N/A	Code this approach in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to communicate your thought process clearly during interviews.

How to Present

Step 1: Clarify the problem constraints and examples.Step 2: Explain the brute force approach to build intuition.Step 3: Discuss inefficiencies and introduce the idea of tracking cooldowns with a map or heap.Step 4: Present the optimal greedy solution using a hash map to track earliest next available days.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 3min → Approach discussion: 7min → Code: 10min → Test & optimize: 5min. Total ~25min

What the Interviewer Tests

The interviewer tests your understanding of cooldown constraints, ability to optimize scheduling, and skill in using appropriate data structures like hash maps and heaps.

Common Follow-ups

• What if tasks can be executed out of order? → Use a priority queue to always pick the earliest available task.
• How to handle multiple tasks with the same cooldown? → Track each task's next available day separately in the map.

💡 These follow-ups test your ability to generalize the solution and handle more complex scheduling scenarios.

🔍

Pattern Recognition

When to Use

1) Tasks with cooldown or spacing constraints, 2) Need to schedule tasks in order, 3) Must track earliest availability, 4) Use hash map or heap to track next available time

Signature Phrases

cooldown periodearliest day to executetasks must be spaced by at least space units

NOT This Pattern When

Problems that require DP for counting sequences or problems without cooldown constraints

Similar Problems

Task Scheduler I (Leetcode 621) - similar cooldown scheduling but with task reordering allowedMinimum Number of Arrows to Burst Balloons - interval scheduling with greedyMeeting Rooms II - scheduling intervals with earliest end time

Practice

1. Given the following Python code for MedianFinder, what is the median after adding numbers 1, 5, and 2 in that order?

easy

A. 1.5

B. 2.0

C. 2

D. 3

Solution

1. Step 1: Insert 1

   low = [-1], high = [], median = 1 (only one element)

2. Step 2: Insert 5

   5 > 1, so push to high: high = [5], low = [-1]. Balanced heaps, median = (1 + 5)/2 = 3.0

3. Step 3: Insert 2

   2 <= 5 but > 1, so push to low: low = [-2, -1], high = [5]. Balance: low_size=2, high_size=1, median = top of low = 2.0

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Median after 3 inserts is 2.0 -> [OK]

Hint: Median after odd inserts is top of larger heap [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Incorrect median calculation for odd number of elements
• Confusing max-heap sign inversion

2. Consider the following buggy code snippet for sliding window median using a balanced sorted list. Which line contains the subtle bug that causes incorrect median results for even-sized windows?

medium

A. Line with 'return float(window[k // 2 - 1] + window[k // 2])'

B. Line with 'bisect.insort_left(window, nums[i])'

C. Line with 'idx = bisect.bisect_left(window, nums[i - k])'

D. Line with 'window = sorted(nums[:k])'

Solution

1. Step 1: Analyze median calculation for even k

   Median for even k is average of two middle elements, so sum must be divided by 2.

2. Step 2: Identify bug

   Line returning sum without division causes median to be twice the correct value.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing division by 2 in even median calculation [OK]

Hint: Even median requires averaging two middle elements [OK]

Common Mistakes:

• Forgetting to divide sum by 2 for even k median
• Incorrect index calculation for median
• Wrong removal or insertion causing imbalance

3. What is the time complexity of the optimal balanced two heaps approach for the sliding window median problem with input size n and window size k?

medium

A. O(n log k)

B. O(n * k log k)

C. O(n log n)

D. O(n * k)

Solution

1. Step 1: Identify operations per element

   Each element is inserted and removed once from heaps, each operation O(log k).

2. Step 2: Calculate total complexity

   For n elements, total time is O(n log k), better than brute force O(n k log k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Logarithmic heap operations per element yield O(n log k) [OK]

Hint: Heap operations cost O(log k) per element [OK]

Common Mistakes:

• Confusing k with n in complexity
• Assuming sorting each window is optimal
• Ignoring heap balancing cost

4. Suppose employees can have overlapping intervals that are not sorted within their schedules, and intervals can be reused or repeated. Which modification to the optimal approach is necessary to correctly find employee free time?

hard

A. Use a min-heap to merge intervals from each employee's schedule without flattening all intervals at once.

B. Sort intervals within each employee before flattening, then flatten and merge all intervals as usual.

C. Flatten all intervals without sorting, then merge overlapping intervals in a single pass.

D. Ignore repeated intervals since they do not affect free time calculation.

Solution

1. Step 1: Understand problem variant

   Intervals within employees are unsorted and may repeat, so flattening without sorting leads to incorrect merges.

2. Step 2: Evaluate approaches

   Sorting each employee's intervals then flattening (A) is costly and may not handle repeats efficiently. Flattening without sorting (C) breaks merging logic. Ignoring repeats (D) risks missing overlaps. Using a min-heap to merge sorted intervals from each employee (B) handles unsorted input and duplicates correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap merging handles unsorted and repeated intervals efficiently [OK]

Hint: Min-heap merging handles unsorted, repeated intervals [OK]

Common Mistakes:

• Flattening without sorting
• Ignoring duplicates
• Sorting all intervals repeatedly

5. Suppose the problem is modified so that each element in the array can be used multiple times (reused) to form a multiset, and you want to minimize the deviation of the multiset's elements after allowed operations. Which modification to the optimal max-heap approach is necessary to handle this variant correctly?

hard

A. Switch to a min-heap and double even numbers instead of halving max

B. No change needed; the original max-heap approach works as is

C. Track counts of each element and update min_val accordingly when reusing elements

D. Use dynamic programming to consider all reuse combinations explicitly

Solution

1. Step 1: Understand reuse impact on deviation calculation

   Reusing elements means multiple copies affect min and max values, so counts must be tracked.

2. Step 2: Modify heap approach to track counts

   Track counts of elements in heap and update min_val carefully when elements are reused or halved to maintain correct deviation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Counting duplicates ensures correct min and max tracking with reuse [OK]

Hint: Reusing elements requires tracking counts to update min and max correctly [OK]

Common Mistakes:

• Assuming original approach works without tracking duplicates
• Switching heap type incorrectly
• Trying brute force reuse without pruning