Course Schedule

Title: Course Schedule Source: leetcode.com

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

1	2, [[1,0]]

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

2, [[1,0],[0,1]]

1	2, [[1,0],[0,1]]

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.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Hints:

This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS – A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

Java solution

/*https://leetcode.com/problems/course-schedule/*/
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Stack;
public class CourseSchedule
{
    public static void main(String args[])
    {
        int[][] prerequisites = {{0,1},
                                {0,2},
                                {1,2}
                                };
        CourseSchedule cs = new CourseSchedule();
        System.out.println(cs.canFinish(3,prerequisites));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites)
    {
        boolean[] visited = new boolean[numCourses];
        ArrayList<ArrayList<Integer>> adjacencyList = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<numCourses;i++)
        {
            adjacencyList.add(new ArrayList<Integer>());
        }
        for(int i=0;i<prerequisites.length;i++)
        {
            adjacencyList.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        System.out.println(adjacencyList);
        for(int i=0;i<numCourses;i++)
        {
            if(dfsIterativeHasCycle(adjacencyList, new boolean[numCourses], i))
                return false;
        }
        return true;
    }

    public boolean dfsIterativeHasCycle(ArrayList<ArrayList<Integer>> adjacencyList, boolean[] visited, int val)
    {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(val);
        while(!stack.isEmpty())
        {
            int i = stack.pop();
            visited[i] = true;
            System.out.println("i: "+i);
            ArrayList<Integer> list = adjacencyList.get(i);
            for(int j: list)
            {
                System.out.println("j: "+ j +" "+ visited[j]);
                if(visited[j]!=true)
                    stack.push(j);
                else
                {
                    System.out.println("end with true");
                    return true;
                }
            }
        }
        System.out.println("end with false");
        return false;
    }
}

/*https://leetcode.com/problems/course-schedule/*/

import java.util.HashMap;

import java.util.ArrayList;

import java.util.Stack;

public class CourseSchedule

{

public static void main(String args[])

{

int[][] prerequisites = {{0,1},

{0,2},

{1,2}

};

CourseSchedule cs = new CourseSchedule();

System.out.println(cs.canFinish(3,prerequisites));

}

public boolean canFinish(int numCourses, int[][] prerequisites)

{

boolean[] visited = new boolean[numCourses];

ArrayList<ArrayList<Integer>> adjacencyList = new ArrayList<ArrayList<Integer>>();

for(int i=0;i<numCourses;i++)

{

adjacencyList.add(new ArrayList<Integer>());

}

for(int i=0;i<prerequisites.length;i++)

{

adjacencyList.get(prerequisites[i][0]).add(prerequisites[i][1]);

}

System.out.println(adjacencyList);

for(int i=0;i<numCourses;i++)

{

if(dfsIterativeHasCycle(adjacencyList, new boolean[numCourses], i))

return false;

}

return true;

}

public boolean dfsIterativeHasCycle(ArrayList<ArrayList<Integer>> adjacencyList, boolean[] visited, int val)

{

Stack<Integer> stack = new Stack<Integer>();

stack.push(val);

while(!stack.isEmpty())

{

int i = stack.pop();

visited[i] = true;

System.out.println("i: "+i);

ArrayList<Integer> list = adjacencyList.get(i);

for(int j: list)

{

System.out.println("j: "+ j +" "+ visited[j]);

if(visited[j]!=true)

stack.push(j);

else

{

System.out.println("end with true");

return true;

}

System.out.println("end with false");

return false;

}

Rate this post

Coddicted

Course Schedule

Java solution

Leave a Reply Cancel Reply