Max Profit from Two Machines

Intuition

Tasks should be allocated to whichever machine yields more profit for that task. The greedy insight is to process tasks in order of their profit difference |a[i] - b[i]| (largest first), so the most impactful assignments are made while both machines still have capacity. Once a machine is full, all remaining tasks go to the other.

Algorithm

1Create Task objects storing a[i], b[i], and diff = |a[i] - b[i]|.
2Sort tasks by diff descending (highest spread first).
3For each task in order:
4 Assign to machine A if (a[i] >= b[i] and A has capacity) or machine B is full.
5 Otherwise assign to machine B.
6Accumulate profit and increment the respective machine counter.
7Return total profit.

Example Walkthrough

Input: x = 2, y = 2, a = [3, 1, 4, 2], b = [2, 5, 3, 6]

1.Diffs: |3-2|=1, |1-5|=4, |4-3|=1, |2-6|=4.
2.Sorted by diff desc: task(1,5,4), task(2,6,4), task(3,2,1), task(4,3,1).
3.Task(1,5): b>a, B has cap → assign B, profit+=5. countB=1.
4.Task(2,6): b>a, B has cap → assign B, profit+=6. countB=2.
5.Task(3,2): B full → assign A, profit+=3. countA=1.
6.Task(4,3): B full → assign A, profit+=4. countA=2.
7.Total profit = 5+6+3+4 = 18.

Output: 18

Common Pitfalls

•Sorting by diff ensures the greedy choice is globally optimal — without sorting, a locally suboptimal assignment could waste capacity on a high-diff task.
•Machine B fills up before A in this formulation; check countB >= y as the overflow condition.
•Both machines must be checked for capacity before deciding assignment; do not assume one always fills first.

Max Profit from Two Machines.java

Java


import java.util.*;

// Approach: Greedy with sorting by |a[i] - b[i]| descending.
// Tasks with the largest difference are assigned to the machine where they have the higher profit.
// When machine A has capacity and a[i] >= b[i] (or machine B is full), assign to A; otherwise assign to B.
// Sorting ensures the most impactful assignment decisions are made first.
// Time: O(n log n) Space: O(n)

class Solution {

    public int maxProfit(int x, int y, int[] a, int[] b) {
        int n = a.length;
        List<Task> tasks = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            tasks.add(new Task(a[i], b[i]));
        }

        tasks.sort((t1, t2) -> t2.diff - t1.diff);

        int profit = 0;
        int countA = 0, countB = 0;

        for (Task t : tasks) {
            if ((t.a >= t.b && countA < x) || countB >= y) {
                profit += t.a;
                countA++;
            } else {
                profit += t.b;
                countB++;
            }
        }
        return profit;
    }

    static class Task {

        int a, b, diff;

        Task(int a, int b) {
            this.a = a;
            this.b = b;
            this.diff = Math.abs(a - b);
        }
    }
}

Was this solution helpful?