Greedy with sorting/heaps

Joining two ropes costs the sum of their lengths. To join them all at minimal total cost, always join the **two shortest** ropes, and push the joined rope back into a min-heap. The “4 3 2 6” preset costs 5 + 9 + 15 = 29. A long rope is best joined late, because every join it takes part in charges its whole length again.

This is exactly the Huffman merge step with lengths instead of frequencies. The exchange argument is the same: in an optimal order the two shortest ropes are joined first.

1static int connectRopes(int[] ropes) {
2    PriorityQueue<Integer> heap = new PriorityQueue<>();
3    for (int r : ropes) heap.add(r);
4    int cost = 0;
5    while (heap.size() > 1) {
6        int joined = heap.poll() + heap.poll();              // the two shortest ropes
7        cost += joined;
8        heap.add(joined);
9    }
10    return cost;
11}

1static int connectRopes(int[] ropes) {
2    PriorityQueue<Integer> pq = new PriorityQueue<>();
3    for (int r : ropes) pq.add(r);
4    int cost = 0;
5    while (pq.size() > 1) {
6        int merged = pq.poll() + pq.poll();               // always join the two shortest
7        cost += merged;                                   // the cost of a join is the length of the result
8        pq.add(merged);
9    }
10    return cost;
11}

Merging two sorted files of sizes a and b costs a + b record moves, and merging all files pairwise forms a binary tree whose internal nodes are the intermediate files. Total cost is the sum of every internal node's weight, which equals each file's size times its depth in the merge tree. That is the same quantity Huffman minimises, so the optimal merge pattern is again: merge the two smallest files first.

For sizes 20, 30, 10, 5, 30 the merges cost 15, 35, 60 and 95, a total of 205. Merging in the order given instead (20 and 30, then add 10, 5 and 30 in turn) would cost 50 + 60 + 65 + 95 = 270.

A **k-way** merge combines k files at once. The greedy rule becomes: merge the k smallest. If the file count does not satisfy (n - 1) mod (k - 1) = 0, pad with zero-size files at the front first so every merge is full; this is the standard fix for k-ary Huffman codes too.

1static int mergeCost(int[] sizes, int k) {
2    PriorityQueue<Integer> heap = new PriorityQueue<>();
3    for (int s : sizes) heap.add(s);
4    while ((heap.size() - 1) % (k - 1) != 0) heap.add(0);    // pad so every merge combines exactly k files
5    int cost = 0;
6    while (heap.size() > 1) {
7        int merged = 0;
8        for (int i = 0; i < k; i++) merged += heap.poll();
9        cost += merged;
10        heap.add(merged);
11    }
12    return cost;
13}

1static int connectRopes(int[] ropes) {
2    PriorityQueue<Integer> pq = new PriorityQueue<>();
3    for (int r : ropes) pq.add(r);
4    int cost = 0;
5    while (pq.size() > 1) {
6        int merged = pq.poll() + pq.poll();               // always join the two shortest
7        cost += merged;                                   // the cost of a join is the length of the result
8        pq.add(merged);
9    }
10    return cost;
11}

Given tasks with a duration and a deadline, can they all be finished on one machine in time? Sort by **deadline** (earliest deadline first, EDF) and run them back to back: the schedule is feasible exactly when every task's finish time is at most its deadline. EDF is optimal because swapping two adjacent tasks that are out of deadline order never makes the later of the two finish later than its deadline.

The same rule also minimises the **maximum lateness** (how far past a deadline any task finishes) when all tasks must run: EDF gives the smallest possible maximum lateness. The next lesson animates the harder variant where some tasks must be dropped.

1// tasks[i] = {duration, deadline}
2static boolean canFinishAll(int[][] tasks) {
3    int[][] a = tasks.clone();
4    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));      // earliest deadline first
5    int time = 0;
6    for (int[] t : a) {
7        time += t[0];
8        if (time > t[1]) return false;
9    }
10    return true;
11}
12
13static int maxLateness(int[][] tasks) {
14    int[][] a = tasks.clone();
15    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));
16    int time = 0, worst = 0;
17    for (int[] t : a) {
18        time += t[0];
19        worst = Math.max(worst, time - t[1]);                // negative lateness counts as zero
20    }
21    return worst;
22}

1static int maxTasks(int[][] tasks) {                  // tasks[i] = {duration, deadline}
2    Arrays.sort(tasks, Comparator.comparingInt(a -> a[1]));      // earliest deadline first
3    PriorityQueue<Integer> chosen = new PriorityQueue<>(Collections.reverseOrder());   // durations of the chosen tasks
4    int time = 0;
5    for (int[] t : tasks) {
6        chosen.add(t[0]); time += t[0];
7        if (time > t[1]) time -= chosen.poll();                  // too late: drop the longest chosen task
8    }
9    return chosen.size();
10}

When not every task fits, which largest set of tasks can finish by their deadlines? Process tasks in deadline order and keep a **max-heap of the durations** taken so far with their total time. Add each task; if the total exceeds the current deadline, drop the longest task taken so far (which might be the new one). Dropping the longest frees the most time while losing only one task.

The “Swap out the longest task” preset (duration:deadline pairs 10:20, 20:50, 30:60, 10:15) finishes 3 of 4: after the 30-minute task joins, the total of 70 exceeds its deadline of 60, so the longest task taken (the 30) is swapped out. “Classic” finishes 4 of 5, and “Nothing fits” finishes 0.

1// courses[i] = {duration, lastDay}
2static int scheduleCourse(int[][] courses) {
3    int[][] a = courses.clone();
4    Arrays.sort(a, Comparator.comparingInt(x -> x[1]));      // by deadline
5    PriorityQueue<Integer> taken = new PriorityQueue<>(Collections.reverseOrder());
6    int time = 0;
7    for (int[] c : a) {
8        taken.add(c[0]);
9        time += c[0];
10        if (time > c[1]) time -= taken.poll();               // drop the longest task taken so far
11    }
12    return taken.size();
13}

1static int maxTasks(int[][] tasks) {                  // tasks[i] = {duration, deadline}
2    Arrays.sort(tasks, Comparator.comparingInt(a -> a[1]));      // earliest deadline first
3    PriorityQueue<Integer> chosen = new PriorityQueue<>(Collections.reverseOrder());   // durations of the chosen tasks
4    int time = 0;
5    for (int[] t : tasks) {
6        chosen.add(t[0]); time += t[0];
7        if (time > t[1]) time -= chosen.poll();                  // too late: drop the longest chosen task
8    }
9    return chosen.size();
10}