You are given a list of tasks to complete in order. Each day you can complete one task. After completing a task of type t, you must wait at least space days before doing another task of the same type. You may insert idle days as needed. Return the minimum number of days to finish all tasks.

Examples

Example 1:

Input: tasks = [1,2,1,2,3,1], space = 3
Output: 9
Explanation:
  Day 1: task 1
  Day 2: task 2
  Day 3: idle (task 1 needs 3-day gap)
  Day 4: idle
  Day 5: task 1
  Day 6: task 2
  Day 7: task 3
  Day 8: idle
  Day 9: task 1

Example 2:

Input: tasks = [5,8,8,5], space = 2
Output: 6
Explanation:
  Day 1: task 5
  Day 2: task 8
  Day 3: idle (task 8 needs 2-day gap)
  Day 4: idle
  Day 5: task 8
  Day 6: task 5

Constraints

  • 1 <= tasks.length <= 10^5
  • 1 <= tasks[i] <= 10^9
  • 1 <= space <= tasks.length

Thinking Process

We must process tasks in order (no reordering). For each task, either:

  1. Enough time has passed since the last same-type task – do it on the next day (day + 1)
  2. Not enough time – we must wait, jumping to lastSeen[t] + space + 1

A hash map tracking the last day each task type was performed gives us O(1) lookup per task.

Walk-through

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

task 1: first time → day=1, lastSeen[1]=1
task 2: first time → day=2, lastSeen[2]=2
task 1: day-lastSeen[1] = 2-1 = 1 ≤ 3 → day=1+3+1=5, lastSeen[1]=5
task 2: day-lastSeen[2] = 5-2 = 3 ≤ 3 → day=2+3+1=6, lastSeen[2]=6
task 3: first time → day=7, lastSeen[3]=7
task 1: day-lastSeen[1] = 7-5 = 2 ≤ 3 → day=5+3+1=9, lastSeen[1]=9

Answer: 9 ✓
Greedy choice pick locally best after sorting

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Sort + greedy (this problem) O(n log n) O(1) Interval scheduling, assignment
Local greedy choice O(n) O(1) Jump game, gas station
Greedy + heap O(n log n) O(n) Merge streams, room allocation
Exchange argument O(n) O(1) Prove greedy choice is safe

Solution

class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        unordered_map<int, long long> lastSeen;
        long long day = 0;

        for (int t : tasks) {
            if (lastSeen.find(t) == lastSeen.end()) {
                day += 1;
            } else {
                if (day - lastSeen[t] <= space) {
                    day = lastSeen[t] + space + 1;
                } else {
                    day += 1;
                }
            }
            lastSeen[t] = day;
        }
        return day;
    }
};

Solution Explanation

Approach: Sort + greedy (this problem)

Key idea: We must process tasks in order (no reordering). For each task, either:

How the code works:

  1. Enough time has passed since the last same-type task – do it on the next day (day + 1)
  2. Not enough time – we must wait, jumping to lastSeen[t] + space + 1

Walkthrough — input tasks = [1,2,1,2,3,1], space = 3, expected output 9:

Day 1: task 1 Day 2: task 2 Day 3: idle (task 1 needs 3-day gap) Day 4: idle Day 5: task 1 Day 6: task 2 Day 7: task 3 Day 8: idle Day 9: task 1

Key Details

Why lastSeen[t] + space + 1? If the last occurrence was on day d, the earliest we can do the same task again is day d + text{space} + 1 (the gap of space days between them).

Why long long? With 10^5 tasks and each potentially adding space (≤ 10^5) idle days, the total days can reach sim 10^{10}.

Why not just day++ always? When we need to wait, we jump forward in time. This is a simulation that skips idle days rather than counting them one by one, keeping the algorithm O(n).

Common Mistakes

  • Using int for day (overflows when many idle days accumulate)
  • Checking day - lastSeen[t] < space instead of <= space (off-by-one: need at least space days between, meaning space + 1 total)
  • Trying to reorder tasks (the problem requires tasks to be completed in the given order)

Key Takeaways

  • “Execute in order with cooldown per type” = greedy simulation with last-seen tracking
  • Jump forward instead of incrementing through idle days – keeps it O(n) regardless of space size
  • Unlike LC 621 Task Scheduler (which allows reordering), this problem fixes the order, making it a simpler simulation

References

Template Reference