Minimum time taken by each job to be completed given by a Directed Acyclic Graph

The problem, simply

You have V jobs. Every job takes exactly 1 minute. Some arrows say "this job must be finished before that job can start". The arrows never go round in a circle, so the jobs can always be done.

As many jobs as you like can run at the same time. For every job, give back the earliest minute at which it can be finished.

A story to remember it

Picture it

Examples

Way 1: the simple way

Give every job the number 1. Then keep walking over all the arrows and fix any job that finished too early.

1. Set time[v] = 1 for every job.
2. Look at every arrow u > v. If time[u] + 1 is bigger than time[v], raise time[v] to it.
3. Repeat step 2 until a full pass changes nothing. The longest chain has at most V jobs, so at most V passes are needed.

class JobTimesRounds {
    public static int[] minTime(int n, int[][] edges) {
        int[] time = new int[n];
        Arrays.fill(time, 1);                         // every job takes at least 1 minute
        for (int round = 0; round < n; round++) {
            boolean changed = false;
            for (int[] e : edges) {
                int u = e[0], v = e[1];
                if (time[u] + 1 > time[v]) {          // v cannot finish before u does
                    time[v] = time[u] + 1;
                    changed = true;
                }
            }
            if (!changed) break;                      // nothing moved, all times are final
        }
        return time;
    }
}

How long it takes: up to V passes over E arrows, O(V * E). Extra room: only the time array, O(V). It is correct, but it keeps looking at arrows whose jobs are already settled.

Way 2: the clever way

Use Mom's sticky notes. Handle a job only after all the jobs it waits for are done, so each job is handled once and each arrow is looked at once. Doing jobs in an order where every arrow points forward is called a topological order, and the sticky note count is the in-degree.

1. Count, for every job, how many arrows point into it. That is its sticky note.
2. Every job whose note says 0 finishes at minute 1. Put it in a waiting line (a queue).
3. Take a job u from the front. For each arrow u > v: set time[v] = max(time[v], time[u] + 1), and cross one off v's note.
4. When v's note reaches 0, all its jobs are done, so time[v] is final. Put v in the line.

class JobTimesKahn {
    public static int[] minTime(int n, int[][] edges) {
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < n; i++) next.add(new ArrayList<>());
        int[] waiting = new int[n];                   // the sticky note
        for (int[] e : edges) {
            next.get(e[0]).add(e[1]);
            waiting[e[1]]++;
        }

        int[] time = new int[n];
        Queue<Integer> ready = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (waiting[i] == 0) { time[i] = 1; ready.add(i); }
        }

        while (!ready.isEmpty()) {
            int u = ready.poll();                     // time[u] is final now
            for (int v : next.get(u)) {
                time[v] = Math.max(time[v], time[u] + 1);
                if (--waiting[v] == 0) ready.add(v);  // all of v's jobs are done
            }
        }
        return time;
    }
}

How long it takes: each job joins the line once and each arrow is followed once, O(V + E). Extra room: the arrow lists, the notes and the line, O(V + E).

Watch out for

• Jobs numbered from 1. Many judges use 1 to N. Make arrays of size N + 1 or subtract 1.
• A job with no arrows in finishes at minute 1, not 0.
• If the arrows had a circle, some notes would never reach 0. Count how many jobs left the line; if it is less than V, report a cycle.
• Reading the size of the line level by level also works: everything in level k finishes at minute k. Both give the same answer.

What interviewers ask next

• Jobs take different amounts of time. Use time[v] = max(time[v], time[u] + dur[v]), starting with time[v] = dur[v]. The largest value is the length of the critical path.
• What is the earliest the whole project ends? The largest finish time, which is also the number of jobs on the longest chain.
• You only have k workers. Now it is much harder. For small V, use dynamic programming over subsets of finished jobs (LeetCode "Parallel Courses II").
• Can you do it with depth first search? Yes. time[v] = 1 + max(time[u]) over the jobs v waits for, with memo so each job is solved once. Same O(V + E).

Remember this

Grown-up words: the jobs and arrows form a directed acyclic graph (DAG), the sticky note is the in-degree, the order the jobs leave the line is a topological order (Kahn's algorithm), and the finish time is the longest path ending at that job.