Resource allocation

Each job takes one unit of time, has a deadline and a profit, and only one job runs per slot. Maximise total profit. Sort jobs by **profit descending** and place each in the **latest free slot at or before its deadline**; skip it if no such slot is free. Placing late keeps earlier slots open for jobs with tighter deadlines.

The “Classic” preset (deadline:profit pairs 2:100, 1:19, 2:27, 1:25, 3:15) earns 142 from 3 jobs: profit 100 takes slot 2, 27 takes slot 1, the jobs with deadline 1 find no slot, and 15 takes slot 3. “All want slot 1” shows that only the most profitable job fits.

The slot search here is a simple scan, so the worst case is O(n · maxDeadline). A union-find structure over slots reduces the search to nearly constant time per job; that structure is covered later in the course.

1// jobs[i] = {deadline, profit}; returns the maximum total profit
2static int jobSequencing(int[][] jobs) {
3    int[][] a = jobs.clone();
4    Arrays.sort(a, (x, y) -> Integer.compare(y[1], x[1]));   // most profitable first
5    int maxDeadline = 0;
6    for (int[] j : a) maxDeadline = Math.max(maxDeadline, j[0]);
7    boolean[] taken = new boolean[maxDeadline + 1];          // slots 1..maxDeadline
8    int total = 0;
9    for (int[] j : a) {
10        for (int slot = j[0]; slot >= 1; slot--) {           // latest free slot not after the deadline
11            if (!taken[slot]) { taken[slot] = true; total += j[1]; break; }
12        }
13    }
14    return total;
15}

1static int maxProfit(int[][] jobs) {                  // jobs[i] = {deadline, profit}, each takes one time slot
2    Arrays.sort(jobs, (a, b) -> Integer.compare(b[1], a[1]));    // most profitable first
3    int maxDeadline = Arrays.stream(jobs).mapToInt(j -> j[0]).max().getAsInt();
4    boolean[] taken = new boolean[maxDeadline + 1]; int profit = 0;
5    for (int[] j : jobs) {
6        for (int slot = j[0]; slot >= 1; slot--) {                // latest free slot on or before the deadline
7            if (!taken[slot]) { taken[slot] = true; profit += j[1]; break; }
8        }
9    }
10    return profit;
11}

Items have weights and values and the thief may take **any fraction** of an item. Sort by value per unit weight, take whole items from the best down, and take a fraction of the first item that does not fit. The “Classic (capacity 50)” preset (weight:value pairs 10:60, 20:100, 30:120) takes the first two whole and two thirds of the third: 60 + 100 + 80 = 240.

This succeeds because the exchange argument works: if the bag holds some of a worse-ratio item while a better-ratio item is not fully taken, swapping a little weight from the worse to the better item raises the value. With whole items only (0/1 knapsack) the swap may be impossible, and greedy fails; that problem is solved by dynamic programming later in this part.

1// items[i] = {weight, value}
2static double fractionalKnapsack(int[][] items, int capacity) {
3    int[][] a = items.clone();
4    Arrays.sort(a, (x, y) -> Double.compare((double) y[1] / y[0], (double) x[1] / x[0]));
5    double value = 0;
6    int room = capacity;
7    for (int[] it : a) {
8        if (room == 0) break;
9        int take = Math.min(room, it[0]);                    // whole item, or whatever room is left
10        value += (double) it[1] * take / it[0];
11        room -= take;
12    }
13    return value;
14}

1static double maxValue(int[] w, int[] v, int capacity) {
2    Integer[] idx = new Integer[w.length]; for (int i = 0; i < idx.length; i++) idx[i] = i;
3    Arrays.sort(idx, (a, b) -> Double.compare((double) v[b] / w[b], (double) v[a] / w[a]));   // best value per weight first
4    double value = 0; int room = capacity;
5    for (int i : idx) {
6        if (room == 0) break;
7        int take = Math.min(room, w[i]);                         // the whole item, or the fraction that fits
8        value += (double) v[i] * take / w[i];
9        room -= take;
10    }
11    return value;
12}

Trains have arrival and departure times; how many platforms are needed so no train waits? Sort arrivals and departures **separately** and sweep with two pointers: if the next arrival is before the next departure, a platform is needed (count++), otherwise a train has left (count--). The maximum count is the answer. This is the event sweep, developed fully in Chapter 22, applied to trains.

The tie rule matters. In the half-open model a train leaving at time 3 frees the platform for one arriving at 3, so the “Back-to-back: half-open needs 1” preset needs 1 platform; if the station needs a gap between trains (closed intervals) the same data needs 2. The animation lets you switch the option and watch the answer change.

1static int minPlatforms(int[] arrival, int[] departure) {
2    int[] arr = arrival.clone(), dep = departure.clone();
3    Arrays.sort(arr);
4    Arrays.sort(dep);
5    int platforms = 0, best = 0, j = 0;
6    for (int i = 0; i < arr.length; i++) {
7        while (dep[j] <= arr[i]) { j++; platforms--; }        // half-open: leaving at t frees the platform for an arrival at t
8        platforms++;
9        best = Math.max(best, platforms);
10    }
11    return best;
12}

1static int maxConcurrent(int[][] iv, boolean closed) {
2    List<int[]> events = new ArrayList<>();                          // {coordinate, +1 start / -1 end}
3    for (int[] x : iv) { events.add(new int[]{x[0], +1}); events.add(new int[]{x[1], -1}); }
4    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0])
5                       : closed ? Integer.compare(b[1], a[1]) : Integer.compare(a[1], b[1]));   // tie: closed -> start first; half-open -> end first
6    int active = 0, best = 0;
7    for (int[] e : events) {
8        active += e[1];                                              // a start opens one, an end closes one
9        best = Math.max(best, active);
10    }
11    return best;
12}

Stations sit on a circle; station i has gas[i] fuel and the leg to the next station costs cost[i]. Find the station to start from to complete the circuit, or report that none exists. Two observations give an O(n) algorithm. If total gas is less than total cost, no start works. Otherwise, a start exists, and it is found by scanning: keep the running tank; whenever it goes negative at station i, no station between the current start and i can be the answer, so restart from i + 1.

The first preset (gas 1 2 3 4 5, cost 3 4 5 1 2) restarts twice and ends with start station 3. “Impossible” has total net fuel -1, so the algorithm stops at once.

1static int canCompleteCircuit(int[] gas, int[] cost) {
2    int total = 0, tank = 0, start = 0;
3    for (int i = 0; i < gas.length; i++) {
4        int net = gas[i] - cost[i];
5        total += net;
6        tank += net;
7        if (tank < 0) { start = i + 1; tank = 0; }           // stations start..i cannot be the start
8    }
9    return total >= 0 ? start : -1;
10}

1static int startStation(int[] gas, int[] cost) {
2    int total = 0, tank = 0, start = 0;
3    for (int i = 0; i < gas.length; i++) {
4        int gain = gas[i] - cost[i];                    // net fuel at this stop
5        total += gain; tank += gain;
6        if (tank < 0) { start = i + 1; tank = 0; }      // cannot reach i + 1 from the current start: restart after i
7    }
8    return total >= 0 ? start : -1;                     // enough fuel overall means the last candidate works
9}

Each child has a greed factor (the smallest cookie size that satisfies them) and each cookie has a size. Each child gets at most one cookie. To satisfy as many children as possible, sort both lists and match the **smallest sufficient cookie** to the **least greedy unsatisfied child**: offer each cookie in increasing order, and give it to the current child only if it is big enough.

A larger cookie can always replace a smaller one in any solution, so using the smallest cookie that works loses nothing: the exchange argument again. The “Match smallest first” preset satisfies all 4 children.

1static int findContentChildren(int[] greed, int[] cookies) {
2    int[] g = greed.clone(), s = cookies.clone();
3    Arrays.sort(g);
4    Arrays.sort(s);
5    int child = 0;
6    for (int cookie : s) {
7        if (child < g.length && cookie >= g[child]) child++; // this cookie satisfies the least greedy child left
8    }
9    return child;
10}

1static int satisfied(int[] greed, int[] cookies) {
2    Arrays.sort(greed); Arrays.sort(cookies);
3    int child = 0;
4    for (int cookie : cookies) {                          // smallest cookie first
5        if (child < greed.length && cookie >= greed[child]) child++;   // it satisfies the least greedy child left
6    }                                                      // otherwise this cookie is too small for everyone left: discard it
7    return child;
8}