coding challenges · advanced

Task Scheduler — Topo Sort + Critical Path

Microsoft task-scheduler design (Make-like). Model tasks as a DAG (dependency→dependent edges). getExecutionOrder uses Kahn's algorithm: enqueue indegree-0 tasks, pop→append→decrement dependents, enqueue new zeros — O(V+E). Cycle detection is free: if the processed count is less than the task count, a circular dependency blocked the rest. getMinCompletionTime with unlimited cores is the critical (longest) path: in topological order, finish[n] = max(finish over deps) + duration[n], and the answer is the max finish time — linear because the topo order guarantees deps are computed first. Limited cores turns it into list scheduling (min-heap of ready tasks; minimizing makespan is NP-hard). Equivalent to LeetCode Course Schedule + Parallel Courses.

🔑 Key line

Build scheduler = DAG. Execution order = Kahn's topological sort (queue indegree-0, decrement dependents); cycle detection is free (processed count < total). Min time on unlimited cores = critical/longest path: in topo order finish[n]=max(finish[deps])+dur[n], answer=max finish. Both O(V+E). Limited cores → list scheduling (NP-hard makespan).

The code

// Build scheduler (à la Make): tasks with duration + deps.
struct Task { std::string name; int dur; std::vector<std::string> deps; };

// 1) Topological order via Kahn (BFS on indegree).
std::vector<std::string> order(const std::vector<Task>& ts) {
    std::unordered_map<std::string, std::vector<std::string>> adj;  // dep -> dependents
    std::unordered_map<std::string, int> indeg;
    for (auto& t : ts) indeg.emplace(t.name, 0);
    for (auto& t : ts) for (auto& d : t.deps) { adj[d].push_back(t.name); indeg[t.name]++; }
    std::queue<std::string> q;
    for (auto& [n, d] : indeg) if (d == 0) q.push(n);
    std::vector<std::string> out;
    while (!q.empty()) {
        auto n = q.front(); q.pop(); out.push_back(n);
        for (auto& m : adj[n]) if (--indeg[m] == 0) q.push(m);
    }
    if (out.size() != ts.size()) throw std::runtime_error("cycle!");  // not all drained
    return out;
}

// 2) Min completion time, unlimited cores = longest (critical) path.
int minTime(const std::vector<Task>& ts) {
    auto topo = order(ts);                 // reuse (also detects cycle)
    std::unordered_map<std::string, int> dur, finish;
    std::unordered_map<std::string, std::vector<std::string>> deps;
    for (auto& t : ts) { dur[t.name] = t.dur; deps[t.name] = t.deps; }
    int ans = 0;
    for (auto& n : topo) {                  // deps finish before n in topo order
        int start = 0;
        for (auto& d : deps[n]) start = std::max(start, finish[d]);
        finish[n] = start + dur[n];
        ans = std::max(ans, finish[n]);
    }
    return ans;
}

What this lesson walks through

01Model the build as a DAG
02Kahn's topo sort — run the indegree-0 tasks
03Cycle detection is free
04Critical path = longest path in the DAG
05Complexity & the limited-cores twist

Tasks are nodes; 'X depends on Y' is an edge Y→X. A valid run order is a topological sort; the minimum time on unlimited cores is the longest (critical) path; a cycle means no order exists.

See it animated — step by step, at your own pace

Unlock the full interactive walkthrough of Task Scheduler — Topo Sort + Critical Path and 100+ animated C++ interview lessons.

Start free →Already a member? Log in →