Task Scheduler Algorithm: Greedy Algorithm Guide

1. Introduction and Core Concepts

The task scheduler algorithm is a classic greedy algorithm problem that models how to optimally schedule a set of tasks with a cooldown constraint. Given an array of tasks represented by capital letters A-Z and a non-negative integer n representing the cooldown interval, the algorithm determines the minimum number of time intervals required to complete all tasks. The core rule is simple but powerful: after executing a particular task, you must wait at least n intervals before executing the same task again. During this waiting period, you can either execute a different task or remain idle.

This problem, popularized as LeetCode 621 - Task Scheduler, is far more than an interview puzzle. It encapsulates a fundamental scheduling dilemma found in operating systems, manufacturing pipelines, and distributed systems: how to maximize throughput while respecting resource constraints and avoiding conflicts. The greedy nature of the solution lies in its strategy of always prioritizing the most frequent remaining tasks first, which minimizes idle time and leads to a globally optimal schedule. Unlike dynamic programming approaches that explore all possibilities, the greedy choice here is provably optimal.

Understanding the task scheduler algorithm matters because it teaches a critical pattern for resource-constrained optimization. It demonstrates how frequency counting, mathematical modeling, and priority queues can transform a seemingly complex simulation problem into an elegant O(n) formula. For engineers building web servers that throttle API calls, databases that manage concurrent queries, or CPUs that schedule processes, the same principles apply: identify the bottleneck resource, schedule around it, and fill gaps efficiently.

Key Terminology

• Tasks: Units of work labeled by type (e.g., 'A', 'B', 'C'). Tasks of the same type are identical and interchangeable.
• Cooldown Interval (n): The minimum number of intervals that must separate two executions of the same task type. If n = 2, the pattern A -> idle -> idle -> A is valid, but A -> A is not.
• Idle Interval: A time slot where the processor does nothing, inserted only when no valid task is available due to the cooldown constraint.
• Least Interval: The minimum total time (including idle slots) needed to execute all tasks without violating the cooldown.

Why Greedy Works Here

A greedy algorithm makes locally optimal choices at each step with the hope of finding a global optimum. In the task scheduler, the locally optimal choice is to always execute the task with the highest remaining frequency that is not in cooldown. This is optimal because the most frequent task is the bottleneck that determines the minimum number of idle slots required. By scheduling the most constrained tasks as early and as evenly as possible, we leave maximum flexibility to interleave less frequent tasks into the gaps, thereby minimizing wasted idle time. Any schedule that delays a high-frequency task will inevitably create more idle slots later.

2. How It Works

The mechanism of the task scheduler algorithm can be understood through two complementary perspectives: the mathematical formula approach and the simulation approach. Both rely on the same greedy insight but differ in implementation. The formula approach derives the answer directly from task frequencies without constructing the actual schedule, while the simulation approach builds the schedule step-by-step using a max-heap and a cooldown queue.

At its heart, the algorithm revolves around the most frequent task. Let max_freq be the highest frequency of any task, and max_count be the number of tasks that share this maximum frequency. Consider the most frequent task, say 'A' occurring 4 times with n = 2. The ideal arrangement to avoid idle time would space 'A's as far apart as possible: A _ _ A _ _ A _ _ A. This creates max_freq - 1 gaps, each of size n. The total slots required for this skeleton is (max_freq - 1) * (n + 1). The +1 accounts for the task itself in each block. The final block only needs to contain the last occurrence of the most frequent tasks, so we add max_count at the end.

This gives us the foundational formula: intervals = (max_freq - 1) * (n + 1) + max_count. However, this formula assumes we have enough distinct tasks to fill all gaps. If we have many different tasks, the gaps will be completely filled and no idle slots are needed. In that case, the answer is simply the total number of tasks. Therefore, the final answer is max(intervals, len(tasks)). This elegantly handles both idle-heavy and task-heavy scenarios.

The Greedy Scheduling Process

The simulation approach makes the greedy choice explicit. It uses a max-heap to always select the most frequent available task. A separate queue tracks tasks that are in cooldown along with the time when they become available again. At each time tick, the algorithm checks if any cooled-down tasks can be returned to the heap, then pops the most frequent task from the heap, executes it, and pushes it into the cooldown queue if it still has remaining instances. If the heap is empty but tasks remain in cooldown, the processor idles until the next task becomes available. This process continues until all tasks are scheduled.

Visualizing Idle Slots

Idle slots are not a failure of the algorithm but a necessary consequence of the cooldown constraint when task diversity is low. For example, with tasks [A, A, A] and n = 2, we must schedule A -> idle -> idle -> A -> idle -> idle -> A, requiring 7 intervals. No rearrangement can reduce this. The greedy algorithm's job is to prove this lower bound and to guarantee that we never insert more idle slots than absolutely necessary. The key is to use less frequent tasks to fill the gaps created by the most frequent tasks first.

3. Implementation

Implementing the task scheduler algorithm efficiently requires careful handling of frequencies and the cooldown constraint. Below are four distinct Python implementations, progressing from the optimal mathematical solution to a full schedule reconstruction that is useful for debugging and visualization.

Implementation 1: Optimal Mathematical Formula (O(n) Time)

This is the most efficient and commonly expected interview solution. It counts frequencies and applies the greedy formula directly without simulation.

from collections import Counter

def least_interval_formula(tasks, n):
    """
    Calculate least intervals using greedy math formula.
    Time: O(n) where n is number of tasks
    Space: O(1) - Counter holds at most 26 letters
    """
    # Edge case: no cooldown means no idle time needed
    if n == 0:
        return len(tasks)
    
    # Count frequency of each task
    task_counts = Counter(tasks)
    max_freq = max(task_counts.values())
    
    # Count how many tasks have the maximum frequency
    max_count = sum(1 for count in task_counts.values() if count == max_freq)
    
    # Calculate intervals based on most frequent task's skeleton
    # (max_freq - 1) blocks of size (n + 1) plus the last block
    part_count = max_freq - 1
    part_length = n + 1
    empty_slots = part_count * part_length + max_count
    
    # The answer is the maximum of skeleton size and total tasks
    # If we have enough tasks to fill gaps, no idle needed
    return max(len(tasks), empty_slots)

# Example usage
tasks = ["A", "A", "A", "B", "B", "B"]
print(least_interval_formula(tasks, 2))  # Output: 8

Implementation 2: Heap-Based Simulation (Greedy Scheduling)

This approach explicitly simulates the greedy choice using a max-heap. It is more intuitive and can be extended to return the actual schedule.

import heapq
from collections import Counter, deque

def least_interval_heap(tasks, n):
    """
    Simulate scheduling using max-heap and cooldown queue.
    Always picks the most frequent available task (greedy choice).
    """
    if n == 0:
        return len(tasks)
    
    # Python has min-heap, so use negative counts for max-heap
    task_counts = Counter(tasks)
    max_heap = [-count for count in task_counts.values()]
    heapq.heapify(max_heap)
    
    time = 0
    # Queue stores tuples of (remaining_count, available_time)
    cooldown_queue = deque()
    
    while max_heap or cooldown_queue:
        time += 1
        
        # If heap is empty, jump time to next available task
        if not max_heap:
            time = cooldown_queue[0][1]
        
        # Return cooled-down tasks to heap
        if cooldown_queue and cooldown_queue[0][1] <= time:
            # Available time reached, push back to heap
            count, _ = cooldown_queue.popleft()
            heapq.heappush(max_heap, count)
        
        if max_heap:
            # Greedy: execute most frequent available task
            count = heapq.heappop(max_heap)
            count += 1  # Increment because counts are negative
            
            # If tasks of this type remain, put into cooldown
            if count < 0:
                # Next available time is current time + n + 1
                available_time = time + n + 1
                cooldown_queue.append((count, available_time))
    
    return time

# Example: tasks with high frequency bottleneck
print(least_interval_heap(["A","A","A","B","B","B"], 2))  # 8
print(least_interval_heap(["A","A","A","B","B","B"], 0))  # 6

Implementation 3: Reconstructing the Actual Schedule

For system design and debugging, you often need the sequence itself, not just the count. This version returns the schedule with 'idle' markers.

import heapq
from collections import Counter, deque

def schedule_with_order(tasks, n):
    """
    Reconstruct the actual greedy schedule including idle slots.
    Returns list representing execution order.
    """
    if not tasks:
        return []
    
    task_counts = Counter(tasks)
    # Max-heap of (-count, task)
    max_heap = [(-count, task) for task, count in task_counts.items()]
    heapq.heapify(max_heap)
    
    cooldown = deque()  # (available_time, -count, task)
    time = 0
    result = []
    
    while max_heap or cooldown:
        time += 1
        
        # Check if any task cooldown has expired
        if cooldown and cooldown[0][0] <= time:
            _, neg_count, task = cooldown.popleft()
            heapq.heappush(max_heap, (neg_count, task))
        
        if max_heap:
            neg_count, task = heapq.heappop(max_heap)
            result.append(task)
            neg_count += 1  # One instance executed
            
            if neg_count < 0:
                # Task still has remaining instances, enter cooldown
                cooldown.append((time + n + 1, neg_count, task))
        else:
            # No task available, must idle
            result.append("idle")
            # Fast-forward if needed - but we step one by one for clarity
            # Optimization: jump time if heap empty
            if cooldown and cooldown[0][0] > time:
                # Could jump, but for schedule we need to show idles
                pass
    
    return result

# Walkthrough example
schedule = schedule_with_order(["A","A","A","B","B","B"], 2)
print(schedule)  # e.g., ['A', 'B', 'idle', 'A', 'B', 'idle', 'A', 'B']
print(f"Total intervals: {len(schedule)}")

Implementation 4: Sorting-Based Greedy Alternative

This variant sorts frequencies instead of using a heap. It is easier to understand for beginners and has similar performance for the 26-letter constraint.

from collections import Counter

def least_interval_sorting(tasks, n):
    """
    Greedy approach using sorting. Repeatedly sorts to find
    most frequent available task. Less efficient but illustrative.
    """
    if n == 0:
        return len(tasks)
    
    task_counts = Counter(tasks)
    # List of frequencies sorted descending
    frequencies = sorted(task_counts.values(), reverse=True)
    
    time = 0
    # Cooldown tracking: list of (remaining, available_time)
    cooldown = []
    
    while frequencies or cooldown:
        time += 1
        
        # Move cooled-down tasks back to frequencies
        # Check cooldown list for tasks whose time has come
        new_cooldown = []
        for rem, avail in cooldown:
            if avail <= time:
                frequencies.append(rem)
            else:
                new_cooldown.append((rem, avail))
        cooldown = new_cooldown
        
        if frequencies:
            frequencies.sort(reverse=True)
            # Greedy: take most frequent
            current = frequencies.pop(0)
            current -= 1
            
            if current > 0:
                cooldown.append((current, time + n + 1))
        else:
            # Must idle - jump to next available time if possible
            if cooldown:
                # Find earliest available time
                next_time = min(avail for _, avail in cooldown)
                # We will idle until then, but increment time step by step
                # For counting only, we could do: time = next_time - 1
                pass
    
    return time

print(least_interval_sorting(["A","A","A","A","B","B","C","C"], 2))

4. Step-by-Step Example

Let us walk through a concrete example to solidify the greedy logic. Consider tasks = ["A", "A", "A", "B", "B", "B"] and n = 2. We have three As and three Bs, with a cooldown of 2. This means after an 'A', we need two other intervals before another 'A' can execute.

Step 1: Frequency Analysis

First, we count frequencies: A:3, B:3. The maximum frequency max_freq = 3 and two tasks share this frequency, so max_count = 2 (both A and B). Using the formula: (3 - 1) * (2 + 1) + 2 = 2 * 3 + 2 = 8. Since total tasks = 6, the answer is max(8, 6) = 8. This tells us we need at least 2 idle slots.

Step 2: Greedy Construction

Now let us simulate the heap approach interval by interval. We initialize a max-heap with [-3, -3] and time = 0.

Time 1: Heap has A:3, B:3. Greedily pick A (tie-break arbitrarily). Execute A. Remaining A:2 goes to cooldown until time 4. Schedule: [A]. Heap: [-3 (B)]

Time 2: Cooldown queue has A until 4. Heap has B. Pick B. Execute B. Remaining B:2 goes to cooldown until time 5. Schedule: [A, B]. Heap: []

Time 3: Heap is empty, but cooldown has A (until 4) and B (until 5). No task is available, so we must idle. Schedule: [A, B, idle]. Heap: []

Time 4: A's cooldown expires (4 <= 4), so A:2 returns to heap. Pick A. Execute A. Remaining A:1 goes to cooldown until 7. Schedule: [A, B, idle, A]. Heap: [] (B still in cooldown until 5)

Time 5: B's cooldown expires, B:2 returns. Pick B. Execute B. Remaining B:1 goes to cooldown until 8. Schedule: [A, B, idle, A, B]. Heap: []

Time 6: No task available (A until 7, B until 8). Idle. Schedule: [A, B, idle, A, B, idle]

Time 7: A returns. Execute A. Schedule: [A, B, idle, A, B, idle, A]. Heap: []

Time 8: B returns. Execute B. Schedule: [A, B, idle, A, B, idle, A, B]. Done. Total 8 intervals.

Step 3: Why This Is Optimal

Could we do better by choosing differently at Time 1? Suppose we started with A, A is not allowed at Time 2 anyway, so B is forced. The idle at Time 3 is unavoidable because both A and B are in cooldown and no other task type exists to fill the gap. Any alternative ordering (e.g., B first) yields the same pattern due to symmetry. The greedy choice of always picking the most frequent available task ensures we never waste an opportunity to reduce future idle time. If we had an additional task C, we could have scheduled [A, B, C, A, B, C, A, B] with no idle, but with only two types, idles are mandatory.

This walkthrough highlights the algorithm's core strength: it automatically discovers the minimal idle slots by spacing the bottleneck tasks as evenly as possible and filling gaps with other tasks whenever possible.

5. Complexity Analysis

Understanding the time and space complexity of the task scheduler algorithm is crucial for selecting the right implementation for your constraints. The two main approaches — mathematical formula and heap simulation — have very different performance characteristics.

The formula-based approach is optimal for simply computing the minimum intervals. It requires a single pass to count frequencies and a second pass over at most 26 distinct characters to find the maximum. Its time complexity is linear in the number of tasks and its space is constant. The heap-based simulation is more expensive because it simulates each time interval, which can be much larger than the number of tasks when many idle slots are required.

For the heap simulation, each task is pushed and popped from the heap exactly once. With k distinct task types (k <= 26), heap operations cost O(log k). However, the total time steps can be up to (max_freq - 1)*(n+1) + max_count, which in the worst case is O(max_freq * n). When n is large, this simulation can be significantly slower than the formula.

Detailed Complexity Table

m = number of tasks, k = distinct task types (<=26), T = total intervals including idle (T >= m)

Analysis Insights

The formula method dominates in all cases for the interval-counting problem, achieving O(m) time and O(1) space. It is the preferred solution in interviews and production where only the count is needed. The heap simulation is valuable when the actual schedule order is required, such as in operating system schedulers that must output the dispatch sequence. Its worst case occurs when n is large and task diversity is low, causing many idle intervals to be simulated one by one. An optimization is to jump time forward when the heap is empty instead of iterating through each idle slot, reducing idle simulation to O(k) jumps.

Space complexity remains low across all greedy methods because the alphabet size is bounded. Even the schedule reconstruction only needs O(T) to store the output, which is unavoidable. Brute force is included for comparison to show why greedy is essential — enumerating all permutations is factorial and completely infeasible for m > 10.

6. Variations and Optimizations

The basic task scheduler problem has several important variations that appear in advanced interviews and real systems. Understanding these extensions demonstrates deeper mastery of greedy scheduling.

Variation 1: Task Scheduler with Cooling Interval and Order Constraints

In some systems, tasks have dependencies (e.g., task B cannot start until task A completes). This transforms the problem into a combination of topological sorting and greedy scheduling. The solution uses a priority queue that respects both cooldown and dependency order, often requiring a modified Kahn's algorithm where available tasks are selected greedily by frequency.

Variation 2: Variable Cooldown per Task Type

Instead of a uniform n, each task type might have its own cooldown n_i. For example, a CPU might need 2 cycles after a floating-point operation but only 1 after an integer operation. The formula approach no longer applies directly. The heap simulation generalizes naturally: the cooldown queue stores time + n_i + 1 for each task type, and the greedy choice remains to pick the most frequent available task.

Variation 3: Minimizing Idle vs. Minimizing Makespan with Release Times

When tasks have release times (they become available at different times) or deadlines, the objective shifts. The greedy strategy may need to incorporate Earliest Deadline First (EDF) or Shortest Processing Time logic alongside frequency. These are no longer pure task scheduler problems but belong to the broader family of scheduling theory.

Key Optimizations

• Time Jumping: Instead of incrementing time by 1 during idle periods, jump directly to cooldown_queue[0].available_time. This reduces worst-case time from O(T) to O(m).
• Frequency Bucket Optimization: Since task types are limited to 26, you can use an array of size 26 and avoid heap overhead entirely by scanning for the max frequency in O(26) = O(1) per step.
• Mathematical Early Exit: If max_freq is small relative to len(tasks) / (n+1), you can immediately return len(tasks) without computing the full formula, as gaps will definitely be filled.
• Cache-Friendly Counting: Use a fixed-size list [0]*26 instead of Counter for slightly better constant factors in performance-critical systems like embedded schedulers.

These optimizations are particularly relevant in high-frequency trading systems or real-time operating systems where scheduler overhead must be minimized to microseconds.

7. Real-World Applications

While the LeetCode problem uses abstract letters, the underlying greedy scheduling pattern solves concrete problems across multiple domains. The core idea — spacing identical operations to avoid resource contention while maximizing utilization — is universal.

CPU and Thread Scheduling

Modern CPUs use task scheduling to avoid pipeline hazards and thermal throttling. For instance, executing the same type of floating-point instruction repeatedly may require a cooldown to prevent overheating a specific execution unit. The operating system's scheduler interleaves different process types to keep all cores busy, exactly like filling idle slots with different tasks. The Completely Fair Scheduler (CFS) in Linux uses similar greedy heuristics to balance load.

Web Servers and Rate Limiting

API gateways and web servers must enforce rate limits: a single client cannot make the same API call more than N times per second. To maximize throughput, the server greedily schedules requests from different clients or different endpoints during the cooldown window of a throttled client. This prevents a single abusive client from blocking the server while ensuring fair usage.

Database and Network Systems

In databases, write operations to the same row or index may require a lock cooldown to ensure consistency. A transaction scheduler will interleave writes to different rows to avoid idle waiting. In networks, packet schedulers avoid sending consecutive packets from the same flow to prevent buffer bloat and ensure Quality of Service (QoS) for all flows.

These applications share a common trait: the cost of violating the cooldown is high (overheating, data corruption, rate-limit violation), but idle time is also expensive. The greedy task scheduler finds the optimal balance, proving that a simple frequency-based priority is sufficient for optimal resource utilization in many constrained systems.

8. Comparison with Alternatives

The task scheduler's greedy approach is one of several scheduling paradigms. Choosing the right one depends on the system's goals: minimizing total time, ensuring fairness, or meeting deadlines. Understanding the trade-offs is essential for system design interviews.

When to Choose Task Scheduler Greedy

Choose the task scheduler greedy algorithm when you have uniform-length tasks with a uniform cooldown constraint and your objective is to minimize total completion time including idle slots. It is superior to FCFS and SJF in this specific constrained setting because those algorithms do not account for the cooldown and will produce invalid schedules or suboptimal makespans. Round Robin provides fairness but introduces unnecessary context switches when cooldown is the main constraint. For systems where tasks have varying durations or deadlines, you would need to combine the frequency-based greedy choice with deadline-aware heuristics, moving beyond the classic task scheduler formulation.

9. Common Mistakes and Best Practices

Even experienced engineers make subtle errors when implementing the task scheduler algorithm. Recognizing these pitfalls is key to writing correct and efficient code.

Common Mistakes

• Forgetting the max() with len(tasks): Many implementations return only (max_freq - 1)*(n+1) + max_count without comparing to len(tasks). This fails when there are enough distinct tasks to fill all idle slots. For example, tasks = [A,B,C,D,E,F], n=2 should return 6, not 4.
• Off-by-One in Cooldown Calculation: The next available time is current_time + n + 1, not current_time + n. If n=2 and you execute at time 1, the next valid time is 4 (needs 2 intervals in between: times 2 and 3). Using +n instead of +n+1 underestimates idle time.
• Using Min-Heap Without Negation: Python's heapq is a min-heap. Forgetting to negate counts when pushing/popping leads to scheduling the least frequent task first, which is the opposite of the greedy optimal and increases idle time.
• Not Handling n=0 Correctly: When n=0, no cooldown exists and the answer is simply len(tasks). Failing to handle this edge case can cause division by zero or unnecessary heap simulation.
• Re-sorting Instead of Heap: Repeatedly sorting the frequency array in each iteration leads to O(T * k log k) instead of O(T log k). While acceptable for k=26, it is inefficient and considered non-idiomatic.
• Ignoring max_count: Counting only one task with max frequency and forgetting that multiple tasks may share the maximum. For [A,A,A,B,B,B] with n=2, max_count=2, not 1, which changes the result from 7 to 8.

Best Practices

• Prefer the Formula for Counting: If you only need the minimum intervals, always use the O(n) formula method. It is simpler, faster, and less error-prone than simulation. Reserve heap simulation for when you need the actual schedule order.
• Use Counter and Fixed-Size Arrays: For the 26 uppercase letters constraint, collections.Counter or a list of size 26 is ideal. Avoid manual dictionary handling.
• Implement Time Jumping: In simulation, when the heap is empty, jump time to the next cooldown expiry instead of iterating idle one by one. This is critical for large n.
• Write Comprehensive Tests: Test edge cases: n=0, single task type, all distinct tasks, large n with few tasks, and max_count > 1. Example test cases: (["A"], 2) -> 1, (["A","A","A"], 2) -> 7, (["A","B","C"], 2) -> 3.
• Document the Greedy Choice: Add comments explaining why picking the most frequent task is optimal. This helps reviewers and interviewers understand your reasoning and proves correctness.
• Separate Concerns: Keep frequency counting, formula calculation, and schedule reconstruction as separate functions for modularity and testability.

Following these practices ensures your implementation is not only correct but also production-ready and easy to maintain. The task scheduler is a great example of how a deep understanding of the problem's structure leads to a dramatically simpler solution than brute force simulation.

10. Interview Questions

The task scheduler algorithm is a favorite in technical interviews because it tests greedy thinking, heap usage, and mathematical insight. Here are common questions and how to approach them.

Question 1: Calculate Least Intervals (LeetCode 621)

Given tasks = ["A","A","A","B","B","B"], n = 2, what is the least number of intervals?

Answer Strategy: State the formula max(len(tasks), (max_freq -1)*(n+1)+max_count). Here max_freq=3, max_count=2, so (2*3+2)=8. Answer is 8. Explain the skeleton: A B idle A B idle A B. Mention edge case n=0. Provide O(n) code with Counter. Interviewers expect you to derive the formula, not just memorize it — explain the gaps concept.

Question 2: Return the Actual Schedule Order

Instead of just the count, return one valid schedule with minimum length, using "idle" for empty slots.

Answer Strategy: Use heap + cooldown queue simulation as shown in Implementation 3. Walk through the example step by step, showing how you always pick the most frequent available task and idle when necessary. Discuss time jumping optimization. Complexity is O(T log k) time and O(T) space for the output. This tests ability to extend the counting solution to construction.

Question 3: What If Tasks Have Different Cooldowns?

Suppose each task type has its own cooldown n_i. How would you modify the algorithm?

Answer Strategy: Explain that the formula no longer works because gaps are non-uniform. The greedy heap simulation generalizes: store (available_time = current_time + n_i + 1) per task type in the cooldown queue. The greedy choice (most frequent available) remains optimal. Complexity stays O(T log k). This tests understanding of algorithm limitations and adaptability.

Question 4: Prove Why Greedy Is Optimal

Why does always picking the most frequent available task lead to the global optimum?

Answer Strategy: Use an exchange argument: Assume an optimal schedule exists that at some point picks a less frequent task X over a more frequent available task Y. Swapping X and Y cannot increase idle time because Y is more constrained (needs more spacing). Repeating this exchange transforms any optimal schedule into the greedy schedule without worsening it, proving greedy is optimal. Also argue that max_freq determines the lower bound of idle slots, and greedy achieves this bound.

Question 5: How Would You Handle Tasks with Priorities or Release Times?

What if tasks have priorities or become available at different times?

Answer Strategy: Discuss that pure frequency greedy is no longer sufficient. You would need a composite priority: e.g., priority = frequency_weight * remaining_count + deadline_weight. For release times, tasks not yet released cannot be in the heap. You would add a release queue and only push tasks to the heap when current_time >= release_time. This becomes a variant of scheduling with constraints, often requiring a more complex priority queue or even NP-hard in some formulations. Mention that you would clarify requirements and propose a heuristic if optimal is infeasible.