Java code for Course Schedule


  • 2
    S
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            if (numCourses <= 1 || prerequisites.length == 0
    				|| prerequisites[0].length == 0) {
    			return true;
    		}
    		int[] course = new int[numCourses];
    		Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
    		for (int i = 0; i < prerequisites.length; i++) {
    			int val = prerequisites[i][0];
    			int key = prerequisites[i][1];
    			if (!map.containsKey(key)) {
    				map.put(key, new ArrayList<Integer>());
    			}
    			map.get(key).add(val);
    			course[val]++;
    		}
    		Queue<Integer> queue = new LinkedList<Integer>();
    		for (int i = 0; i < numCourses; i++) {
    			if (course[i] == 0) {
    				queue.add(i);
    			}
    		}
    		while (!queue.isEmpty()) {
    			int cur = queue.poll();
    			if (map.get(cur) != null) {
    				for (int temp : map.get(cur)) {
    					course[temp]--;
    					if (course[temp] == 0) {
    						queue.offer(temp);
    					}
    				}
    			}
    		}
    		for (int i = 0; i < numCourses; i++) {
    			if (course[i] != 0) {
    				return false;
    			}
    		}
    		return true;
        }
    }

  • 0
    S

    Thanks for the excellent solution. It seems that course[] is the record for the number of courses needed for course i. The queue is for the ones that don't need any course before these. Also, I like the idea of using while loop to mock the process of taking courses.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.