Home/Data Structures & Algorithms/Greedy & Resource Allocation
  1. Asked: September 11, 2026In: ,

    Task Scheduler with Cooldowns: Closed-form mathematical formula vs Priority Queue simulation

    Anonymous
    Anonymous Begginer

    The Task Scheduler problem is a masterclass in recognizing that the most frequent task dictates the entire schedule structure. 1. Deriving the Formula Visually Suppose our tasks are [A, A, A, B, B, C] with cooldown n = 2. Task A appears most frequently ($count = 3$). Between each A, there must be atRead more

    The Task Scheduler problem is a masterclass in recognizing that the most frequent task dictates the entire schedule structure.

    1. Deriving the Formula Visually

    Suppose our tasks are [A, A, A, B, B, C] with cooldown n = 2.

    Task A appears most frequently ($count = 3$). Between each A, there must be at least n = 2 cooldown slots:

    Frame 1: A _ _
Frame 2: A _ _
Frame 3: A (last occurrence doesn't need trailing cooldown!)

    Notice the structure:

    • There are max_freq - 1 full frames.
    • Each full frame has size n + 1 (the task itself plus its n cooldown slots).
    • The final frame only contains the final occurrences of the most frequent tasks.

    2. The Closed-Form Equation

    Let max_freq be the highest frequency of any task, and max_count be how many tasks tie for that highest frequency (for example, if both A and B appear 3 times, max_count = 2).

    theoretical_min = (max_freq - 1) * (n + 1) + max_count

    What if there are so many other tasks that no CPU idle slots are needed?

    If you have tons of diverse tasks (e.g. [A, A, B, B, C, D, E, F, G, H]), they easily fill up all idle slots, and the CPU never needs to idle at all! In that case, the answer is simply len(tasks).

    Therefore, the global answer is simply:

    ans = max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

    Clean Python 3.12 Implementation (0 CPU Simulation Cycles!)

    from collections import Counter

def least_interval(tasks: list[str], n: int) -> int:
    """Calculates minimum task intervals in O(N) time and O(1) space."""
    counts = Counter(tasks)
    max_freq = max(counts.values())
    
    # Count how many tasks have this maximum frequency
    max_count = sum(1 for count in counts.values() if count == max_freq)

    # Calculate optimal frames
    formula_ans = (max_freq - 1) * (n + 1) + max_count

    # Answer is whichever is larger: formula or total task count
    return max(len(tasks), formula_ans)

    Complexity Breakdown

    • Time Complexity: O(N) to count task frequencies. The mathematical formula itself evaluates in O(1) time!
    • Space Complexity: O(1) auxiliary space, because the alphabet size is bounded by 26 English uppercase letters.
    See less
    • 0
  2. Asked: September 11, 2026In: ,

    Gas Station Circular Tour: Mathematical proof of why a single pass in O(N) is sufficient

    Anonymous
    Anonymous Begginer

    The Gas Station problem is one of the most elegant examples of the Greedy Elimination Proof. Let's break down the mathematical invariant that allows you to skip stations with 100% confidence. 1. The Two Fundamental Theorems Theorem 1: Total Balance Invariant If $sum gas[i] ge sum cost[i]$, there isRead more

    The Gas Station problem is one of the most elegant examples of the Greedy Elimination Proof. Let’s break down the mathematical invariant that allows you to skip stations with 100% confidence.

    1. The Two Fundamental Theorems

    Theorem 1: Total Balance Invariant

    If $sum gas[i] ge sum cost[i]$, there is guaranteed to be at least one valid starting station that completes the entire circuit.

    Why? Because the total net balance $sum (gas[i] – cost[i]) ge 0$. If you graph the cumulative fuel sum along the circle, the lowest dip (the absolute minimum point on the graph) is the optimal starting point! Starting right after that lowest dip means your tank will never dip below zero!

    Theorem 2: The Greedy Skip Invariant

    Suppose you start at station A and successfully reach station B, but you fail to travel from B to B + 1 (your tank drops below 0).

    Claim: No station C between A and B (i.e. $A le C le B$) can be the starting station!

    Proof:

    1. Because you started at A and reached C, the gas you had in your tank upon arriving at C was $ge 0$.
    2. Even with that bonus leftover gas from before C, you still starved and died at B!
    3. If you were to start at C from scratch (with an empty tank, zero bonus gas), you would run out of fuel at or before station B!

    Therefore, every single station from A to B is mathematically disqualified in one fell swoop! The next possible candidate can only be B + 1.

    Clean Python 3.12 Implementation

    def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    """Finds starting gas station index in single pass O(N) time."""
    total_tank = 0
    curr_tank = 0
    starting_station = 0

    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total_tank += diff
        curr_tank += diff

        # If we run out of gas at station i
        if curr_tank < 0:
            # Pick the next station as candidate start
            starting_station = i + 1
            # Reset current tank to 0
            curr_tank = 0

    # If total gas is less than total cost, impossible to complete circle
    return starting_station if total_tank >= 0 else -1

    Complexity Breakdown

    • Time Complexity: O(N). Exactly one single pass through the array. Zero nested loops.
    • Space Complexity: O(1). Exactly 3 scalar integers tracking running totals.
    See less
    • 0