Task Scheduler - Practice Coding Problems

Task Scheduler - Problem

Array Hash Table Greedy Sorting Heap (Priority Queue) Counting Medium

You are given an array of CPU tasks, each represented by letters A-Z, and a number n. Each CPU interval can execute one task or remain idle. Tasks can be completed in any order, but there's a constraint: there must be at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Input & Output

Example 1 — Equal Frequencies

$ Input: tasks = ["A","A","A","B","B","B"], n = 2

› Output: 8

💡 Note: A -> B -> idle -> A -> B -> idle -> A -> B. Need 2 idle intervals between same tasks.

Example 2 — No Cooldown

$ Input: tasks = ["A","A","A","B","B","B"], n = 0

› Output: 6

💡 Note: No cooldown required, so execute all 6 tasks consecutively.

Example 3 — Sufficient Different Tasks

$ Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2

› Output: 12

💡 Note: Enough different tasks to fill gaps: A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> A -> A

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of tasks with cooldown period n

Process

Schedule tasks with n intervals between same types

Output

Minimum total intervals needed

Key Takeaway

🎯 Key Insight: The most frequent task determines the minimum schedule length and creates gaps that other tasks can fill

Asked in

f Facebook 45 a Amazon 38 G Google 32 M Microsoft 28

The key insight is that the most frequent task determines the minimum time structure. The optimal approach uses a mathematical formula to calculate the minimum intervals based on task frequencies and available gaps. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(n)	O(1)	Calculate minimum time using mathematical formula
Greedy with Frequency Counting	O(n * log k)	O(k)	Count task frequencies and arrange greedily by priority
Simulation with Queue	O(tasks.length * n)	O(1)	Simulate the CPU execution step by step using queues

Mathematical Formula — Algorithm Steps

Find maximum frequency
Calculate minimum intervals
Check if other tasks fit in idle slots
Return max of calculated time or total tasks

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Pattern

Most frequent task determines the structure

Calculate Gaps

(max_freq - 1) gaps of size n each

Fill Gaps

Other tasks fill available slots

Code -

solution.c — C

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

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(char* tasks, int taskLen, int n) {
    if (n == 0) return taskLen;
    
    // Count frequency of each task
    int taskCount[26] = {0};
    for (int i = 0; i < taskLen; i++) {
        taskCount[tasks[i] - 'A']++;
    }
    
    // Find maximum frequency
    int maxFreq = 0;
    for (int i = 0; i < 26; i++) {
        if (taskCount[i] > maxFreq) {
            maxFreq = taskCount[i];
        }
    }
    
    // Count tasks with maximum frequency
    int maxFreqCount = 0;
    for (int i = 0; i < 26; i++) {
        if (taskCount[i] == maxFreq) {
            maxFreqCount++;
        }
    }
    
    // Calculate minimum time
    int gaps = maxFreq - 1;
    int availableSlots = gaps * n;
    int remainingTasks = taskLen - maxFreq * maxFreqCount;
    
    int idleTime = max(0, availableSlots - remainingTasks);
    
    return taskLen + idleTime;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char tasks[1000];
    int taskLen = 0;
    
    // Parse JSON array
    for (int i = 0; line[i]; i++) {
        if (line[i] >= 'A' && line[i] <= 'Z') {
            tasks[taskLen++] = line[i];
        }
    }
    
    int n;
    scanf("%d", &n);
    
    int result = solution(tasks, taskLen, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count frequencies plus constant time calculation

✓ Linear Growth

Space Complexity

O(1)

Only use constant extra space for counters

✓ Linear Space

187.0K Views

High Frequency

~25 min Avg. Time

2.8K 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

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler