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? ### What a Strong Answer Covers - A reverse traversal from every target to build the exact induced set of required targets and prerequisites. - Deduplication of shared prerequisites plus cycle detection on the reachable subgraph. - For sequential effort, summing each required course duration exactly once. - For unlimited parallelism, topological dynamic programming for earliest finish times and the maximum target finish time. - Correct treatment of disconnected components and a clear complexity bound in required vertices and edges. ### Follow-up Questions - How would a limit of two simultaneous courses change the problem? - How would you answer many target-list queries over the same course graph? - What changes if a course may choose one of several prerequisite alternatives?