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.

When you have multiple online LCA queries on a static tree, the gold standard is Binary Lifting (used in compiler dominance frontiers, distributed network routing, and Git commit histories).

1. The Core Idea: Powers of 2 Parent Jumps

Instead of storing only a node’s immediate parent (which forces you to step up the tree one node at a time in $O(N)$), what if every node stored its ancestor at distance $2^0, 2^1, 2^2, 2^3, dots, 2^k$?

We define a 2D table: up[u][i] = the (2^i)-th ancestor of node u.

The state transition is pure dynamic programming:

up[u][i] = up[ up[u][i-1] ][i-1]

In English: ‘To jump $2^i$ steps up from $u$, first jump $2^{i-1}$ steps up to reach intermediate node $v$, and then from $v$ jump another $2^{i-1}$ steps!’ ($2^{i-1} + 2^{i-1} = 2^i$).

2. Answering an LCA Query in 2 Steps

To find the LCA of nodes u and v:

1. Level the Depths: If depth[u] < depth[v], swap them. Use binary powers to jump u upwards until depth[u] == depth[v] in $O(log N)$ steps. If u == v, they were on the same branch → return u!
2. Simultaneous Binary Leap: Jump both u and v upwards together using the largest possible power of 2 such that their ancestors are still different (up[u][i] != up[v][i]). When no more jumps can be made, their immediate parent (up[u][0]) is their Lowest Common Ancestor!

Clean C++20 Implementation

#include <vector>
#include <cmath>
#include <algorithm>

class TreeLCA {
    int n, max_log;
    std::vector<int> depth;
    std::vector<std::vector<int>> up;

    void dfs(int u, int p, int d, const std::vector<std::vector<int>>& adj) {
        depth[u] = d;
        up[u][0] = p;
        for (int i = 1; i < max_log; ++i) {
            up[u][i] = up[ up[u][i - 1] ][i - 1];
        }
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1, adj);
            }
        }
    }

public:
    TreeLCA(int nodes, int root, const std::vector<std::vector<int>>& adj) : n(nodes) {
        max_log = std::ceil(std::log2(n)) + 1;
        depth.assign(n, 0);
        up.assign(n, std::vector<int>(max_log, root));
        dfs(root, root, 0, adj);
    }

    int queryLCA(int u, int v) {
        if (depth[u] < depth[v]) std::swap(u, v);

        // Step 1: Bring u and v to same depth
        int diff = depth[u] - depth[v];
        for (int i = 0; i < max_log; ++i) {
            if ((diff >> i) & 1) {
                u = up[u][i];
            }
        }
        if (u == v) return u;

        // Step 2: Jump together
        for (int i = max_log - 1; i >= 0; --i) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
};

Complexity Breakdown

• Preprocessing Time: O(N log N) via a single DFS pass.
• Preprocessing Memory: O(N log N) to store the jump table.
• Per Query Time: Strictly O(log N). For $N = 1,000,000$, $log_2(1,000,000) pprox 20$ operations. You can evaluate 50,000 queries in a fraction of a second!