Matching applications

1static boolean assign(int w, List<Integer>[] canDo, boolean[] seen, int[] workerOf) {
2    for (int j : canDo[w]) {
3        if (seen[j]) continue;
4        seen[j] = true;
5        if (workerOf[j] == -1 || assign(workerOf[j], canDo, seen, workerOf)) { workerOf[j] = w; return true; }
6    }
7    return false;
8}
9// canDo[w] = jobs worker w is able to do; result[w] = the job given to w, or -1
10static int[] assignJobs(int workers, int jobs, List<Integer>[] canDo) {
11    int[] workerOf = new int[jobs];
12    Arrays.fill(workerOf, -1);
13    for (int w = 0; w < workers; w++) assign(w, canDo, new boolean[jobs], workerOf);
14    int[] jobOf = new int[workers];
15    Arrays.fill(jobOf, -1);
16    for (int j = 0; j < jobs; j++) if (workerOf[j] != -1) jobOf[workerOf[j]] = j;
17    return jobOf;
18}

1// project p takes up to capacity[p] students: turn it into capacity[p] identical slots, then match students to slots
2@SuppressWarnings("unchecked")
3static int[] assignToProjects(int[] capacity, int[][] choices) {      // choices[s] = projects student s accepts
4    int slots = 0;
5    int[] projectOfSlot = new int[Arrays.stream(capacity).sum()];
6    for (int p = 0; p < capacity.length; p++) for (int k = 0; k < capacity[p]; k++) projectOfSlot[slots++] = p;
7    List<Integer>[] canDo = new List[choices.length];
8    for (int s = 0; s < choices.length; s++) {
9        canDo[s] = new ArrayList<>();
10        for (int slot = 0; slot < slots; slot++)
11            for (int p : choices[s]) if (projectOfSlot[slot] == p) { canDo[s].add(slot); break; }
12    }
13    int[] slotOf = assignJobs(choices.length, slots, canDo);
14    int[] result = new int[choices.length];                           // the project of each student, or -1
15    for (int s = 0; s < result.length; s++) result[s] = slotOf[s] == -1 ? -1 : projectOfSlot[slotOf[s]];
16    return result;
17}

1// blocked[r][c] = true for a hole. Every domino covers one "black" and one "white" square of the checkerboard,
2// so the most dominoes that fit is a maximum matching between black and white free squares.
3static int maxDominoes(boolean[][] blocked) {
4    int rows = blocked.length, cols = blocked[0].length, count = 0;
5    int[] owner = new int[rows * cols];                               // owner[white] = the black square matched to it, or -1
6    Arrays.fill(owner, -1);
7    for (int r = 0; r < rows; r++)
8        for (int c = 0; c < cols; c++)
9            if ((r + c) % 2 == 0 && !blocked[r][c] && place(r, c, blocked, new boolean[rows * cols], owner)) count++;
10    return count;
11}
12static boolean place(int r, int c, boolean[][] blocked, boolean[] seen, int[] owner) {
13    int cols = blocked[0].length;
14    int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
15    for (int d = 0; d < 4; d++) {
16        int nr = r + dr[d], nc = c + dc[d];
17        if (nr < 0 || nc < 0 || nr >= blocked.length || nc >= cols || blocked[nr][nc] || seen[nr * cols + nc]) continue;
18        seen[nr * cols + nc] = true;
19        int other = owner[nr * cols + nc];
20        if (other == -1 || place(other / cols, other % cols, blocked, seen, owner)) { owner[nr * cols + nc] = r * cols + c; return true; }
21    }
22    return false;
23}

1// job i must run in one of the time slots 0 .. deadline[i] - 1; one job per slot; returns the most jobs that fit
2static int maxOnTimeJobs(int[] deadline, int slots) {
3    int[] jobIn = new int[slots];                                     // the job running in each slot, or -1
4    Arrays.fill(jobIn, -1);
5    int done = 0;
6    for (int i = 0; i < deadline.length; i++) if (run(i, deadline, new boolean[slots], jobIn)) done++;
7    return done;
8}
9static boolean run(int i, int[] deadline, boolean[] seen, int[] jobIn) {
10    for (int t = 0; t < Math.min(deadline[i], jobIn.length); t++) {
11        if (seen[t]) continue;
12        seen[t] = true;
13        if (jobIn[t] == -1 || run(jobIn[t], deadline, seen, jobIn)) { jobIn[t] = i; return true; }
14    }
15    return false;
16}

1static boolean tryAugment(int u, List<Integer>[] adj, boolean[] seen, int[] matchR) {
2    for (int v : adj[u]) {
3        if (seen[v]) continue;
4        seen[v] = true;
5        if (matchR[v] == -1 || tryAugment(matchR[v], adj, seen, matchR)) { matchR[v] = u; return true; }
6    }
7    return false;
8}
9@SuppressWarnings("unchecked")
10static List<List<Integer>> pathCover(int n, int[][] edges) {          // vertex-disjoint paths that cover every vertex of a DAG
11    List<Integer>[] adj = new List[n];                                // split graph: left copy u (outgoing), right copy v (incoming)
12    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
13    for (int[] e : edges) adj[e[0]].add(e[1]);
14    int[] matchR = new int[n];                                        // matchR[v] = u means the edge u -> v is used by a path
15    Arrays.fill(matchR, -1);
16    for (int u = 0; u < n; u++) tryAugment(u, adj, new boolean[n], matchR);
17    int[] next = new int[n];
18    Arrays.fill(next, -1);
19    for (int v = 0; v < n; v++) if (matchR[v] != -1) next[matchR[v]] = v;
20    List<List<Integer>> paths = new ArrayList<>();
21    for (int v = 0; v < n; v++) {
22        if (matchR[v] != -1) continue;                                // v has no predecessor: a path starts here
23        List<Integer> path = new ArrayList<>();
24        for (int x = v; x != -1; x = next[x]) path.add(x);
25        paths.add(path);
26    }
27    return paths;
28}