Task Scheduler II - Practice Coding Problems

Task Scheduler II - Problem

You are given a 0-indexed array of positive integers tasks, representing tasks that need to be completed in order, where tasks[i] represents the type of the i-th task.

You are also given a positive integer space, which represents the minimum number of days that must pass after the completion of a task before another task of the same type can be performed.

Each day, until all tasks have been completed, you must either:

Complete the next task from tasks, or
Take a break.

Return the minimum number of days needed to complete all tasks.

Input & Output

Example 1 — Basic Case

$ Input: tasks = [1,2,1,2], space = 3

› Output: 6

💡 Note: Day 1: Task 1, Day 2: Task 2, Day 5: Task 1 (wait 3 days), Day 6: Task 2 (wait 3 days)

Example 2 — No Waiting Needed

$ Input: tasks = [5,8,8,5], space = 2

› Output: 7

💡 Note: Day 1: Task 5, Day 2: Task 8, Day 5: Task 8 (wait 2 days), Day 7: Task 5 (wait 2 days)

Example 3 — Single Task Type

$ Input: tasks = [1,1,1], space = 2

› Output: 7

💡 Note: Day 1: Task 1, Day 4: Task 1 (wait 2 days), Day 7: Task 1 (wait 2 days)

Constraints

1 ≤ tasks.length ≤ 10⁵
1 ≤ tasks[i] ≤ 10⁹
0 ≤ space ≤ tasks.length

Visualization

Tap to expand

Understanding the Visualization

Input

Tasks [1,2,1,2] with space=3 cooldown

Process

Schedule tasks with mandatory waiting periods

Output

Minimum 6 days needed to complete all tasks

Key Takeaway

🎯 Key Insight: Use hash map to track last completion day for each task type, enabling O(1) cooldown validation

Asked in

f Facebook 15 G Google 12 a Amazon 8

The key insight is to track the last completion day for each task type using a hash map. When processing a task, check if enough days have passed since its last completion. If not, wait until the cooldown period is over. Best approach is Hash Map Tracking with Time: O(n), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n²)	O(n)	Simulate each day, checking all previous occurrences of each task type
Hash Map Tracking	O(n)	O(k)	Use hash map to track last completion day for each task type

Brute Force Simulation — Algorithm Steps

For each task, search backwards to find last occurrence of same type
Calculate days since last occurrence
If not enough days passed, add break days
Continue until all tasks completed

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Task

For each task, search all completed tasks

Find Last

Find most recent completion of same task type

Wait

Add waiting days if needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* tasks, int tasksSize, int space) {
    if (tasksSize == 0) return 0;
    
    typedef struct {
        long long day;
        int task;
    } completion;
    
    completion* completedDays = malloc(tasksSize * sizeof(completion));
    int completedCount = 0;
    long long currentDay = 1;
    
    for (int i = 0; i < tasksSize; i++) {
        int task = tasks[i];
        
        // Find the last day this task type was completed
        long long lastCompletion = -1;
        for (int j = completedCount - 1; j >= 0; j--) {
            if (completedDays[j].task == task) {
                lastCompletion = completedDays[j].day;
                break;
            }
        }
        
        // Check if we need to wait
        if (lastCompletion != -1 && currentDay - lastCompletion <= space) {
            currentDay = lastCompletion + space + 1;
        }
        
        completedDays[completedCount].day = currentDay;
        completedDays[completedCount].task = task;
        completedCount++;
        currentDay++;
    }
    
    long long result = completedDays[completedCount - 1].day;
    free(completedDays);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int tasks[1000];
    int tasksSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            tasks[tasksSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int space;
    scanf("%d", &space);
    
    printf("%lld\n", solution(tasks, tasksSize, space));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each task, we may need to search through all previous tasks to find the last occurrence

⚠ Quadratic Growth

Space Complexity

O(n)

Store completion days for all tasks in worst case

⚡ Linearithmic Space

18.8K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler