Analyze Minimum Completion Time for Target Courses in a Prerequisite DAG

Interview Prompt

You are given courses, each course's completion time, prerequisite edges, and a list of target courses. Design an algorithm for the minimum time needed to finish the targets. Include only the targets and their transitive prerequisites: courses that merely appear at the same topological level are not automatically required. Handle targets in disconnected prerequisite components. Because “time” can mean total study effort or elapsed time with parallel courses, state the scheduling model and explain the answer under both interpretations.

Constraints & Assumptions

• The prerequisite relation is expected to be a DAG; a reachable cycle makes the requested schedule invalid.
• A shared prerequisite is counted once when several targets depend on it.
• Unrelated courses at the same level must be excluded from the required subgraph.
• Disconnected required components must be identified rather than forced into one artificial dependency chain.

Clarifying Questions to Ask

• Can multiple available courses be taken in parallel, or does time mean total person-hours?
• Does each duration represent elapsed completion time, required effort, or both?
• Must every target itself be completed, and may one target be a prerequisite of another?
• What should be returned when a target is unknown or a reachable cycle exists?