-
Notifications
You must be signed in to change notification settings - Fork 383
Expand file tree
/
Copy pathParallel Courses.java
More file actions
35 lines (35 loc) · 1.22 KB
/
Parallel Courses.java
File metadata and controls
35 lines (35 loc) · 1.22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public int minimumSemesters(int n, int[][] relations) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
int[] indegree = new int[n];
for (int[] relation : relations) {
int course = relation[0];
int dependency = relation[1];
indegree[course - 1]++;
graph.computeIfAbsent(dependency, k -> new HashSet<>()).add(course);
}
Queue<Integer> queue = new LinkedList<>();
int numOfSemesters = 0;
int coursesTaken = 0;
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.add(i + 1);
}
}
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
int removed = queue.remove();
coursesTaken++;
for (Integer dependent : graph.getOrDefault(removed, new HashSet<>())) {
indegree[dependent - 1]--;
if (indegree[dependent - 1] == 0) {
queue.add(dependent);
}
}
}
numOfSemesters++;
}
return coursesTaken == n ? numOfSemesters : -1;
}
}