Task Scheduler II

Task Scheduler II

What is this problem about?

Task Scheduler II is a variation of the original problem with a slightly different constraint. You are given an array of task types that must be completed in the given order. You are also given a space integer, representing the minimum number of days that must pass before you can repeat the same task type. Unlike the first problem, you cannot reorder tasks to minimize idle time; you must simply find the earliest day you can complete the last task while following the order and the cooldown rules.

Why is this asked in interviews?

This question is common in interviews at Uber and Meta to test a candidate's ability to handle chronological simulations and hash map tracking. It evaluates how you manage "state" (the last time a task was performed) and how you update a global clock. It’s a practical problem that mirrors real-world constraints in job scheduling where order of operations is fixed but resource cooldowns apply.

Algorithmic pattern used

The primary pattern is the Simulation with a Hash Table.

1. Initialize a current_day = 0.
2. Use a Hash Map to store the last_completed_day for each task type.
3. For each task in the input:
   • current_day++.
   • Check the Hash Map: if this task was done at last_day, the next available day is last_day + space + 1.
   • If current_day is less than this available day, jump current_day to the available day.
   • Update the Hash Map with the new current_day for this task type.

Example explanation

Tasks: [1, 2, 1, 2], space = 3.

1. Task 1: Day 1. Map: {1: 1}.
2. Task 2: Day 2. Map: {1: 1, 2: 2}.
3. Task 1: Minimum next day for type 1 is 1 + 3 + 1 = 5. Current day is 3. Jump to Day 5. Map: {1: 5, 2: 2}.
4. Task 2: Minimum next day for type 2 is 2 + 3 + 1 = 6. Current day is 6 (since we just did task 1 at Day 5, the next task starts at Day 6). Jump to Day 6. Map: {1: 5, 2: 6}. Result: 6 days.

Common mistakes candidates make

A common mistake is trying to use the complex greedy logic from Task Scheduler I. Since the order is fixed here, the logic is much simpler but requires careful day tracking. Another error is an "off-by-one" calculation for the cooldown period (e.g., using last_day + space instead of last_day + space + 1).

Interview preparation tip

For the Task Scheduler II coding problem, focus on how to efficiently skip time. Instead of incrementing the clock day by day (which is O(total_time)), jump directly to the next available day. This ensures your solution remains O(n) relative to the number of tasks. Mastery of the Hash Table interview pattern is key here.