Question

link

有n个任务需要完成（编号1到n），任务之间有一些依赖关系，如果任务a依赖于任务b和c，那么只有当任务b和任务c完成之后才能完成任务a。给定所有的依赖关系，判断这些任务是否能够完成。如果能够完成，请给出一个合法的任务完成序列。

样例：

n=5

1->2,3

3->4

上述样例中任务1依赖于任务2和任务3，任务3依赖于任务4，那么存在合法的任务完成序列4,3,2,1,5

Solution

Classic topology sorting, refer to this nice answer.

My Code

public int[] myJobSchedulerWithoutQueue(Map<Integer, List<Integer>> deps,
        int n) {
    int[] ans = new int[n];

    int[] depCount = new int[n];
    // eg. job 1 depends on job 2 and 3, thus depCount[1-1] = 2
    Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
    // graph would be reversed version of deps, used for topology sorting
    // eg. 2 would point to 1, and 3 would points to 1
    for (int i : deps.keySet()) {
        depCount[i - 1] = deps.get(i).size();
        for (int j : deps.get(i)) {
            // add (j, i) pair into graph
            if (!graph.containsKey(j)) {
                graph.put(j, new ArrayList<Integer>());
            }
            graph.get(j).add(i);
        }
    }
    // now we got depCount[] and graph ready, let's rock
    int sorted = 0;
    while (sorted != n) {
        // first find a 'p' so that depCount[p] = 0
        int p = 0;
        while (p < n && depCount[p] != 0) {
            p++;
        }
        if (p == n) {
            // unable to find a new node to sort, sorting failed
            break;
        }
        // remember p is only the index, the value should be +1
        int val = p + 1;
        ans[sorted++] = val;
        depCount[p] = -1;
        if (graph.containsKey(val)) {
            for (int i : graph.get(val)) {
                depCount[i - 1]--;
            }
        }
    }
    if (sorted == n)
        return ans; // sort sucess
    else
        return null; // sort failed
}

The following is very similar implementation, but using a Queue to store temporary nodes.

public int[] myJobSchedulerWithQueue(Map<Integer, List<Integer>> deps, int n) {
    int[] ans = new int[n];

    int[] depCount = new int[n];
    // eg. job 1 depends on job 2 and 3, thus depCount[1-1] = 2
    Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
    // graph would be reversed version of deps, used for topology sorting
    // eg. 2 would point to 1, and 3 would points to 1
    for (int i : deps.keySet()) {
        depCount[i - 1] = deps.get(i).size();
        for (int j : deps.get(i)) {
            // add (j, i) pair into graph
            if (!graph.containsKey(j)) {
                graph.put(j, new ArrayList<Integer>());
            }
            graph.get(j).add(i);
        }
    }
    // now we got depCount[] and graph ready, let's rock
    int sorted = 0;
    Queue<Integer> queue = new LinkedList<Integer>();
    while (sorted != n) {
        for (int i = 0; i < depCount.length; i++) {
            if (depCount[i] == 0) {
                queue.offer(i + 1);
                depCount[i] = -1;
            }
        }
        if (queue.isEmpty()) {
            break; // sorting failed
        }
        int val = queue.poll();
        ans[sorted++] = val;
        if (graph.containsKey(val)) {
            for (int i : graph.get(val)) {
                depCount[i - 1]--;
            }
        }
    }
    if (sorted == n)
        return ans; // sort sucess
    else
        return null; // sort failed
}