Work Order Lead Time: Critical Path Through an Operations DAG to Shipping

A manufacturing work order is modeled as a directed acyclic graph. Each node is an operation, such as machining or inspection, that takes a whole number of days. Each edge (source, target) is a dependency: operation target cannot start until operation source has finished. Every path ends at a single terminal node of type "shipping".

Operations that do not depend on each other can run at the same time, so the total lead time of the work order is its critical path length: the longest path from any starting node (a node with no incoming edges) to the shipping node. Return the lead time.

Function Signature

def work_order_lead_time(nodes: list[tuple[str, str, int]], edges: list[tuple[str, str]]) -> int:

Each node is (id, type, duration), with duration in days, and each edge is (source, target).

Rules

• The length of a path is the sum of the durations of all nodes on it, including its first node and the shipping node.
• A starting node is a node with no incoming edges. If the work order contains only the shipping node, that node alone forms the only path.
• Return the maximum length over all paths that begin at a starting node and end at the shipping node.
• Node types other than "shipping" do not affect the result.

Constraints

• 1 <= len(nodes) <= 10^4
• 0 <= len(edges) <= 5 * 10^4
• 0 <= duration <= 1000 for every node.
• Node ids are unique, nonempty strings of at most 20 characters. Types are nonempty lowercase strings.
• Exactly one node has type "shipping", and it has no outgoing edges.
• Every edge connects two different existing nodes, and no edge appears twice.
• The graph has no cycles, and every node has a directed path to the shipping node.
• The answer is at most 10^7.

Examples

Example 1

Input: nodes = [("m1", "machining", 2), ("m2", "machining", 4), ("i1", "inspection", 1),
 ("m3", "machining", 3), ("i2", "inspection", 2), ("ship", "shipping", 0)]
 edges = [("m1", "i1"), ("m2", "i1"), ("i1", "m3"), ("i1", "i2"),
 ("m3", "ship"), ("i2", "ship"), ("m1", "i2")]
Output: 8

The starting nodes are m1 and m2. The longest path is m2 -> i1 -> m3 -> ship, with length 4 + 1 + 3 + 0 = 8. The other paths are shorter: for example, m1 -> i1 -> m3 -> ship has length 6, m2 -> i1 -> i2 -> ship has length 7, and m1 -> i2 -> ship has length 4.

Example 2

Input: nodes = [("x", "machining", 1), ("y", "machining", 1), ("z", "inspection", 1),
 ("w", "machining", 5), ("ship", "shipping", 1)]
 edges = [("x", "y"), ("y", "z"), ("z", "ship"), ("w", "ship")]
Output: 6

The chain x -> y -> z -> ship has more operations but length 4, while w -> ship has length 5 + 1 = 6.

Example 3

Input: nodes = [("ship", "shipping", 2)], edges = []
Output: 2

The shipping node is the only node, so the lead time is its own duration.