Help !! Why this code is TLE


  • 0
    M

    The basic idea is like topological sort, use maps to store if Course N is taken, it could releases a set of courses.

     public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, Set<Integer>> cantake = new HashMap<Integer, Set<Integer>>();
    	HashSet<Integer> remain = new HashSet<Integer>();
    	HashSet<Integer> finished = new HashSet<Integer>();
    
    	for (int i = 0; i < prerequisites.length; ++i) {
    		remain.add(prerequisites[i][0]);
    		if (cantake.containsKey(prerequisites[i][1])) {
    			cantake.get(prerequisites[i][1]).add(prerequisites[i][0]);
    		} else {
    			Set<Integer> list = new HashSet<Integer>();
    			list.add(prerequisites[i][0]);
    			cantake.put(prerequisites[i][1], list);
    		}
    	}
    	
    	for (int i = 0; i < numCourses; ++i)
    		if (!remain.contains(i))
    			finished.add(i);
    			
    	for (int i = 0; i < numCourses; i++) {
    
    		int size = finished.size();
    
    		for (int taking : cantake.keySet()) {
    			if (finished.contains(taking)) {
    				finished.addAll(cantake.get(taking));
    			}
    		}
    
    // If unchanged, break;
    		if (size == finished.size())
    			break;
    
    	}
    	return finished.size() == numCourses;
    }

Log in to reply
 

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