Google Coding Question: Task Scheduling with Precedence

You must compute the minimal time to finish a set of tasks that have durations and precedence constraints given as a DAG. Two variants are asked: (1) unlimited identical CPUs (any number of tasks can run in parallel once predecessors finish) and (2) at most M identical CPUs (concurrent tasks limited to M). You are given n tasks, a list of directed edges (i -> j) describing precedence, and integer durations t_i > 0.

For the unlimited-CPU case you should compute the makespan (C_max). The canonical solution is to compute longest-path (critical-path) distances on the DAG using a topological ordering and dynamic programming: the earliest finish time for a node = max(earliest finish of predecessors) + t_i. That gives an optimal integer makespan in O(n + |E|) time.

For the M-CPU case you must respect both precedence and a resource bound. This version is NP-hard in general (identical machines with precedence constraints to minimize makespan). In interviews you’ll be expected to (a) explain hardness, (b) propose practical algorithms: greedy list scheduling (activate ready tasks and assign up to M by priority), priority heuristics such as largest remaining processing time or longest-path-first (critical-path priority), or a binary-search-on-makespan feasibility check with a simulation. Also discuss exact approaches for small instances (DP over subsets or time-indexed DP) and approximation guarantees (Graham-type bounds).

Skills signaled: topological sort, DAG longest path (critical path), greedy scheduling, simulation, complexity analysis, and trade-offs between exact and heuristic/approximate solutions. Be prepared to produce code for the unlimited case, a simulator for the M-CPU heuristic, and to discuss correctness and edge cases.