Exercise contract#
Given a finite mapping from declared string task IDs to nonnegative integer durations and prerequisite edges u->v, return every task's earliest finish time assuming unlimited parallel workers and time zero availability. Duplicate edges are ignored. Reject an edge containing an unknown task ID and reject a negative duration. If any directed cycle exists, including in a disconnected component, return a cycle error. Do not invent scheduling limits or tie-dependent finish times.
Constraints
- 0 <= number of tasks <= 100,000 and task IDs are distinct nonempty strings.
- 0 <= number of supplied edges <= 300,000 before duplicate removal.
- Each duration is an integer in [0, 1,000,000,000].
- Every resulting finish time fits a signed 64-bit integer; Python integers are unbounded and Java uses long.
- Unlimited parallel workers means unrelated ready tasks may begin at the same time.
Examples
durations={a:2,b:3,c:4}, edges=[a->c,b->c]- {a:2,b:3,c:7}a and b start at zero. c waits for the later prerequisite b at time 3, then finishes at 7.
durations={a:1,b:1}, edges=[a->b,b->a]- cycle errorNo topological schedule can process both declared tasks.
Derive the approach#
Baseline: Repeatedly scan every unfinished task to find one whose prerequisites are complete, then rescan all prerequisites to compute its start. This can take O(VE) work and still needs a reliable no-progress cycle check.
- Create one adjacency set per declared task. Insert each edge once so duplicates do not inflate indegrees.
- Initialize earliestStart[task]=0 and enqueue every task with indegree zero.
- When task u is processed, finish[u]=earliestStart[u]+duration[u]. For every edge u->v, maximize earliestStart[v] with finish[u].
- Decrement v's indegree once for the unique edge; enqueue v when all prerequisites have been processed.
- If the processed count is smaller than the declared task count, at least one component contains a cycle. Otherwise return finishes for every declared task, including isolated tasks.
- Time
- O(V + E) expected after duplicate normalization, where E is the number of unique edges.
- Space
- O(V + E) for adjacency sets, indegrees, queue, and timing maps.
- Assumptions
- Hash/set operations are expected O(1); Java long is sufficient for every path-duration sum by contract; no worker-capacity or scheduling overhead is modeled.
Three-stage hint ladder#
Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.
Reveal hint 1
Observation: unlimited workers remove resource contention, so a task waits only for its latest-finishing prerequisite.
Reveal hint 2
Invariant/data structure: process unique edges in topological order; store each task's maximum completed-prerequisite finish and remaining indegree.
Reveal hint 3
Transition/pseudocode: finish u, maximize every dependent's start with finish[u], decrement its indegree, enqueue at zero, then compare processed count with all declared tasks.
Reference solutions#
Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.
Reveal tested Python reference
from collections import deque
def earliest_finishes(durations, edges):
if any(not task or duration < 0 for task, duration in durations.items()):
raise ValueError("task IDs must be nonempty and durations nonnegative")
graph = {task: set() for task in durations}
indegree = {task: 0 for task in durations}
for source, target in edges:
if source not in durations or target not in durations:
raise ValueError("edge contains an unknown task")
if target not in graph[source]:
graph[source].add(target)
indegree[target] += 1
earliest_start = {task: 0 for task in durations}
finish = {}
ready = deque(task for task in durations if indegree[task] == 0)
while ready:
task = ready.popleft()
finish[task] = earliest_start[task] + durations[task]
for dependent in graph[task]:
earliest_start[dependent] = max(earliest_start[dependent], finish[task])
indegree[dependent] -= 1
if indegree[dependent] == 0:
ready.append(dependent)
if len(finish) != len(durations):
raise ValueError("cycle")
return {task: finish[task] for task in durations}Reveal tested Java reference
import java.util.ArrayDeque;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
final class TransferT07 {
record Edge(String source, String target) {}
static Map<String, Long> earliestFinishes(Map<String, Long> durations, List<Edge> edges) {
Map<String, Set<String>> graph = new LinkedHashMap<>();
Map<String, Integer> indegree = new LinkedHashMap<>();
for (Map.Entry<String, Long> task : durations.entrySet()) {
if (task.getKey().isEmpty() || task.getValue() < 0) throw new IllegalArgumentException("invalid task");
graph.put(task.getKey(), new LinkedHashSet<>());
indegree.put(task.getKey(), 0);
}
for (Edge edge : edges) {
if (!durations.containsKey(edge.source()) || !durations.containsKey(edge.target())) {
throw new IllegalArgumentException("unknown task");
}
if (graph.get(edge.source()).add(edge.target())) {
indegree.put(edge.target(), indegree.get(edge.target()) + 1);
}
}
Map<String, Long> earliestStart = new LinkedHashMap<>();
Queue<String> ready = new ArrayDeque<>();
for (String task : durations.keySet()) {
earliestStart.put(task, 0L);
if (indegree.get(task) == 0) ready.add(task);
}
Map<String, Long> finish = new LinkedHashMap<>();
while (!ready.isEmpty()) {
String task = ready.remove();
long taskFinish = earliestStart.get(task) + durations.get(task);
finish.put(task, taskFinish);
for (String dependent : graph.get(task)) {
earliestStart.put(dependent, Math.max(earliestStart.get(dependent), taskFinish));
indegree.put(dependent, indegree.get(dependent) - 1);
if (indegree.get(dependent) == 0) ready.add(dependent);
}
}
if (finish.size() != durations.size()) throw new IllegalArgumentException("cycle");
Map<String, Long> ordered = new LinkedHashMap<>();
for (String task : durations.keySet()) ordered.put(task, finish.get(task));
return ordered;
}
}Deterministic test plan#
| Case | Input | Expected | What it catches |
|---|---|---|---|
| worked-example | {a:2,b:3,c:4}; a->c,b->c | {a:2,b:3,c:7} | Maximum prerequisite finish. |
| isolated-and-zero | {solo:5,zero:0}; no edges | {solo:5,zero:0} | Isolated tasks and zero duration. |
| zero-duration-chain | {a:0,b:0,c:2}; a->b,b->c | {a:0,b:0,c:2} | Zero does not stall indegree processing. |
| duplicate-edge | {a:2,b:3}; a->b twice | {a:2,b:5} | Duplicate does not inflate indegree. |
| empty-plan | {}; no edges | {} | Empty declared task set. |
| unknown-id | {a:1}; a->missing | ValueError / IllegalArgumentException | Reject undeclared endpoints. |
| negative-duration | {a:-1}; no edges | ValueError / IllegalArgumentException | Reject negative duration. |
| cycle | {a:1,b:1}; a->b,b->a | cycle error | No ready task. |
| disconnected-cycle | {free:1,a:1,b:1}; a->b,b->a | cycle error | Processing an acyclic component does not hide another component's cycle. |
Transfer and follow-ups#
- Return one critical prerequisite chain ending at the latest-finishing task.
- Add a deterministic topological order while preserving finish times; define the ready-task tie rule.
- Explain why a fixed worker limit changes the problem and invalidates this unlimited-parallel recurrence.
First isolate topological cycle detection, then return to this exercise's DP timing state.
Authorship and review#
Engineering Foundry authored the task-planning context, validation contract, examples, tests, and reference programs. It is not attributed to an employer; topological ordering and DAG dynamic programming are established techniques.
Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.
Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09, SRC-DSA-MIT-6006