Amazon — Task Scheduler (Greedy + Frequency Heap)

Problem (Amazon Top Interview)

Given tasks with a cooldown n (same task can't repeat within n intervals), return the minimum number of intervals to finish all tasks.

Example:

tasks = ["A","A","A","B","B","B"], n = 2
→ 8  (A B _ A B _ A B)

Key Insight — Greedy + Math

The minimum time is either:

len(tasks) if tasks fill naturally
(max_freq - 1) * (n + 1) + count_of_max_freq_tasks

For simulation: use a max-heap of frequencies. On each cycle of (n+1) slots, execute up to (n+1) tasks in decreasing frequency order.

Solutions

Python — O(n) Math

from collections import Counter

def leastInterval(tasks, n):
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for f in freq.values() if f == max_freq)
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

Python — Heap Simulation

import heapq
from collections import Counter, deque

def leastInterval(tasks, n):
    freq = Counter(tasks)
    heap = [-f for f in freq.values()]
    heapq.heapify(heap)
    time = 0
    q = deque()
    while heap or q:
        time += 1
        if q and q[0][1] == time:
            heapq.heappush(heap, q.popleft()[0])
        if heap:
            cnt = heapq.heappop(heap) + 1
            if cnt:
                q.append((cnt, time + n))
    return time

JavaScript

function leastInterval(tasks, n) {
    const freq = new Array(26).fill(0);
    for (const t of tasks) freq[t.charCodeAt(0)-65]++;
    const maxF = Math.max(...freq);
    const maxC = freq.filter(f=>f===maxF).length;
    return Math.max(tasks.length, (maxF-1)*(n+1)+maxC);
}

Java

import java.util.*;
public int leastInterval(char[] tasks, int n) {
    int[] f=new int[26]; for(char t:tasks) f[t-'A']++;
    int maxF=0; for(int x:f) maxF=Math.max(maxF,x);
    int maxC=0; for(int x:f) if(x==maxF) maxC++;
    return Math.max(tasks.length,(maxF-1)*(n+1)+maxC);
}

C++

#include <algorithm>
#include <vector>
using namespace std;
int leastInterval(vector<char>& tasks, int n) {
    int f[26]={};
    for(char t:tasks) f[t-'A']++;
    int maxF=*max_element(f,f+26), maxC=count(f,f+26,maxF);
    return max((int)tasks.size(),(maxF-1)*(n+1)+maxC);
}

C

#include <string.h>
int leastInterval(char* tasks, int n) {
    int f[26]={},sz=strlen(tasks);
    for(int i=0;i<sz;i++) f[tasks[i]-'A']++;
    int maxF=0,maxC=0;
    for(int i=0;i<26;i++) if(f[i]>maxF)maxF=f[i];
    for(int i=0;i<26;i++) if(f[i]==maxF)maxC++;
    int r=(maxF-1)*(n+1)+maxC; return r>sz?r:sz;
}

Complexity

Approach	Time	Space
Math formula	O(N)	O(1)
Heap simulation	O(N log N)	O(N)