Task Scheduler with Cooling Interval

Scheduling tasks under cooling constraints is a common challenge in operating systems, rate-limited APIs, and real-time pipelines. The “Task Scheduler with Cooling Interval” problem exercises frequency counting, greedy scheduling, and heap-based prioritization to minimize idle time.

Problem Statement

Given an array tasks of characters representing task types and a non-negative integer n representing the cooling interval, return the least number of time units the CPU will take to finish all tasks. Between two executions of the same task type, the CPU must wait at least n units of time (which may be idle).

Example:
tasks = [A, A, A, B, B, B], n = 2
One optimal schedule: A → B → idle → A → B → idle → A → B
Total time units = 8

1. Clarify Requirements Before Jumping Into Code

I need to confirm:

• Different letters represent distinct tasks.

• CPU can execute one task or stay idle in each unit.

• Cooling interval n applies only to same task types.

• Return the total time units (including idles).

• Task count can be large, so O(T log M) is acceptable, where T = total tasks, M = distinct tasks.

2. Identify the Category of the Question

This question has aspects to it that sound like a greedy algorithm might serve as well. It also seems possible that the solution might involve some kind of frequency counting aspect to it. Data structures that seem like they might be useful are priority queues/heaps. Some patterns that come to mind based on these ideas:

• Counting task frequencies

• Using a max-heap to pick the most frequent available task

• Balancing idle slots vs. task slots

3. Consider a Brute-Force Approach to Understand the Problem

Brute-force idea:

1. Maintain a list of remaining tasks.

2. At each time unit, scan for a task not executed in the last n units (check history) and pick any.

3. If I can't find any executable tasks, then idle

Checking a history of size n each iteration makes each step O(M + n).

Since I have to do this for every task, my overall runtime is O(T · (M + n)). That's too slow!

4. Brainstorm More Solutions

Let's think about how to optimize. The brute-force solution involves a lot of repeat work: it requires us to rescan the array of tasks on every iteration. Is there a way I can avoid having to scan the entire array?

A data structure might be helpful here, but not just any data structure. I don't need my tasks in a random order like in the brute-force solution - that won't help me minimize time spent idling. So let's assume I need to maintain some kind of ordering of my tasks.

How do I order my tasks, though? That detail might impact the data structure that I settle on. Well, the way this question is worded, there's really only one feature that differentiates the tasks - their frequency. That seems like a decent idea to start - after all, the faster I process the elements with the highest frequency and get them out of the way, the less likely I am to run into a scenario where I'm forced to idle. This is sounding kind of like a greedy algorithm - one where I choose tasks based on their highest frequency.

This presents a problem though - what if I have a million tasks of type A and and only 1 task for types B - Z? The highest frequency element is going to be of type A for a very long time. And if I idle every time my highest frequency element is on cool down, then I'll be idling a lot.

So what's the logical thing to do when your most frequent task is on cool down? Well, you try and execute the next most frequent task, going down the list until you find a task you can execute.

That makes me wonder - assuming there's at least one task in my list that I can process, what's the minimum number of tasks I would need to look at to guarantee I find it?

That probably has something to do with n, my cool down time. Since I only process one task in each time unit, if I were to check my n most frequent tasks, there's a chance that every single one of them could still be on cool down. But what if I check one more, i.e. n+1 tasks? There's no way every single one of them could be on cool down! That's it!

So here's the solution so far:

• Order my tasks based on highest frequency, giving it a size of O(M)

• On each time unit/cycle:

  • Look at the top n+1 tasks.

  • Execute the first task that you find that is not on cool down.

  • Decrement it's count, then resort my tasks

Now let's think about which data structures will store my task frequencies.

Option 1 - Frequency array + sort each cycle

An array is a logical place to start: easy to use and implement. Storing elements can be done in constant time, and popping the n+1 highest frequency tasks is easy as well.

But what about sorting? With an array, I can't just pop the element in and out, I'd have to resort the entire array. That's O(M log M) time per cycle. Since I'm ultimately doing this for every task, that's O(T * M log M).

Option 2 - Max-Heap of frequencies

There's one data structure that shines when we need to maintain an ordering: heaps/priority queues.

With a heap, I don't have to spend O(M log M) resorting my data - I can do it in O(log M) time.

Since everything else about the solution stays the same, that means my runtime is O(T log M).

The Max Heap solution is looking like my best bet!

Side note: there's a third solution here that involves designing a mathematical formula to calculate the answer. It's clever, but I left it off this post because, well... how many of us are really going to be able to derive a mathematical formula in an interview? Not me, that's for sure.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Cycle + sort frequencies	O((T/(n+1))·M log M)	O(M)	Uses only arrays	Sorting each cycle is heavy
Max-heap of task frequencies	O(T log M)	O(M)	Clear, standard greedy pattern	Requires heap data structure

6. Write Pseudocode to Structure Your Thoughts

count = frequency map of tasks
heap = max-heap of counts

time = 0
while heap not empty:
  temp = empty list
  for i in 0 to n:
    if heap not empty:
      freq = heap.pop()
      execute one task: freq -= 1
      temp.add(freq)
    time += 1
    if heap empty and all freqs in temp are zero:
      break  // no more tasks, avoid extra idles
  for f in temp:
    if f > 0:
      heap.push(f)
return time

7. Consider Edge Cases

• n = 0 → no cooling needed; total time = number of tasks.

• Single task type → time = (count - 1)·(n + 1) + 1.

• Many distinct tasks, n large → CPU rarely idles.

• Empty tasks list → time = 0.

8. Write Full Code Syntax

import java.util.*;

public class TaskScheduler {
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char t : tasks) {
            freqMap.put(t, freqMap.getOrDefault(t, 0) + 1);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        heap.addAll(freqMap.values());

        int time = 0;
        while (!heap.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int cycle = n + 1;

            for (int i = 0; i < cycle; i++) {
                if (!heap.isEmpty()) {
                    int f = heap.poll() - 1;
                    if (f > 0) temp.add(f);
                }
                time++;
                if (heap.isEmpty() && temp.isEmpty()) {
                    break;
                }
            }
            for (int f : temp) {
                heap.offer(f);
            }
        }
        return time;
    }
}

9. Test Your Code

public static void main(String[] args) {
    TaskScheduler sol = new TaskScheduler();

    System.out.println(sol.leastInterval(new char[]{'A','A','A','B','B','B'}, 2) == 8);
    System.out.println(sol.leastInterval(new char[]{'A','A','A','B','B','B'}, 0) == 6);
    System.out.println(sol.leastInterval(new char[]{'A','A','A','A','A','A','B','C','D','E','F','G'}, 2) == 16);
    System.out.println(sol.leastInterval(new char[]{}, 5) == 0);
    System.out.println(sol.leastInterval(new char[]{'A'}, 50) == 1);
}

10. Key Lessons to Remember for Future Questions

• The max-heap + frequency counting pattern solves many “schedule with cooldown” problems.

• Focus on repeat work in your algorithm when you are looking for opportunities to optimize.

• A direct mathematical formula exists, but building the heap-based solution should be enough to get you through the vast majority of interview loops. After all, you're interviewing to be a software engineer, not a mathematician, and the heap-based solution shows a solid understanding of coding fundamentals and data structures.

Good Luck and Happy Coding!