1136. Parallel Courses

 一刷 07/2022

Version #1 Topological Sort

Time O(N + E)

Space O(N + E)

Runtime: 6 ms, faster than 97.21% of Java online submissions for Parallel Courses.

Memory Usage: 43.1 MB, less than 97.94% of Java online submissions for Parallel Courses.

class Solution {

    public int minimumSemesters(int n, int[][] relations) {

        int[] prevCount = new int[n];

        List<Integer>[] nextCourses = new ArrayList[n];

        for (int i = 0; i < n; i++) {

            nextCourses[i] = new ArrayList<>();

        }

        for (int[] relation : relations) {

            int prev = relation[0] - 1;

            int next = relation[1] - 1;

            nextCourses[prev].add(next);

            prevCount[next]++;

        }

        int taken = 0;

        int semester = 0;

        Queue<Integer> que = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {

            if (prevCount[i] == 0) {

                que.offer(i);

            }

        }

        while (!que.isEmpty()) {

            int size = que.size();

            semester++;

            // 1 - 3 - 2

            while (size-- > 0) {

                int curr = que.poll();

                taken++;

                for (int next : nextCourses[curr]) {

                    prevCount[next]--;

                    if (prevCount[next] == 0) {

                        que.offer(next);

                    }

                }

            }

        }

        return taken == n ? semester : -1;

    }

}