207.-course-schedule.md

207. Course Schedule

Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [aᵢ, bᵢ] indicates that you must take course bᵢ first if you want to take course aᵢ.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation:
There are a total of 2 courses to take.
To take course 1 you should have finished course 0.
So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Explanation:
There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1.
So it is impossible.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= aᵢ, bᵢ < numCourses
• All the pairs prerequisites[i] are unique.

PHP

Result

Runtime: 2 ms, Beats 100.00% of users with PHP.

Memory: 22.41 MB, Beats 96.15% of users with PHP.

class Solution
{
    /**
     * @param  int[][]  $prerequisites
     */
    public function canFinish(int $numCourses, array $prerequisites): bool
    {
        $graph = [];
        $inDegree = array_fill(0, $numCourses, 0);

        for ($i = 0; $i < count($prerequisites); $i++) {
            $end = $prerequisites[$i][0];
            $start = $prerequisites[$i][1];

            $graph[$start][] = $end;
            $inDegree[$end]++;
        }

        $queue = new SplQueue;
        for ($i = 0; $i < count($inDegree); $i++) {
            if ($inDegree[$i] === 0) {
                $queue->enqueue($i);
            }
        }

        $count = 0;
        while (! $queue->isEmpty()) {
            $current = $queue->dequeue();
            $count++;

            if (isset($graph[$current])) {
                foreach ($graph[$current] as $neighbor) {
                    if (--$inDegree[$neighbor] === 0) {
                        $queue->enqueue($neighbor);
                    }
                }
            }

        }

        return $count === $numCourses;
    }
}