FastPrep
Problem · Graph

Minimum Semesters With Course Capacity

Learn this problem
● HardAmazon logoAmazonFULLTIMEONSITE INTERVIEW
See Amazon hiring insights

Problem statement

There are n courses labeled from 1 through n. Each pair [a, b] in prerequisites means course a must be completed before course b.

In one semester, you may take at most maxCourses courses whose prerequisites have all been completed in earlier semesters. Return the minimum number of semesters needed to complete every course.

The prerequisite graph is a directed acyclic graph. When more than maxCourses courses are available, choose the subset that leads to the global minimum rather than relying on a fixed greedy priority.

Function

minimumSemesters(n: int, prerequisites: int[][], maxCourses: int) → int

Examples

Example 1

n = 4prerequisites = [[1,3],[2,3],[3,4]]maxCourses = 2return = 3

Take courses 1 and 2, then course 3, then course 4.

Example 2

n = 4prerequisites = []maxCourses = 2return = 2

With no prerequisites, take any two courses in each semester.

Constraints

  • 1 <= n <= 15
  • 0 <= prerequisites.length <= n * (n - 1) / 2
  • 1 <= maxCourses <= n
  • Every prerequisite pair contains two distinct labels in [1, n].
  • Prerequisite pairs are unique and form a directed acyclic graph.

More Amazon problems

drafts saved locally
public int minimumSemesters(int n, int[][] prerequisites, int maxCourses) {
    // Write your code here.
}
n4
prerequisites[[1,3],[2,3],[3,4]]
maxCourses2
expected3
checking account