Assignment Problems

The Problem That Looks Too Hard for Greedy

You have \(n\) applicants. Applicant \(i\) has programming skill \(P_i\) and artistic skill \(A_i\). You must select exactly \(a\) programmers and exactly \(b\) artists (where \(a + b \leq n\)). Each applicant can fill at most one role. Maximize the total skill sum.

The Greedy Choice: Sort applicants by \(P_i - A_i\) descending. Sweep a split point with two heaps — one tracking the best programmers from the left, one tracking the best artists from the right.

Your first instinct is probably DP or Hungarian algorithm. Maybe min-cost max-flow. And those all work — but they're overkill. Here's something that takes a while to click, but once it does, you'll see assignment problems differently: the exchange argument from previous lessons extends to role assignment, and the algorithm that falls out is a sweep line with two heaps.

The Trap: Greedy by Skill

The most natural wrong approach: sort by programming skill, assign the top \(a\) as programmers, then from the rest pick the top \(b\) by artistic skill.

Try it on this input: \(n=4\), \(a=1\), \(b=1\).

Applicant	\(P_i\)	\(A_i\)
Alice	10	1
Bob	9	100

Greedy-by-P assigns Alice as programmer (10), Bob as artist (100). Total = 110. That's actually optimal here. But what about:

Applicant	\(P_i\)	\(A_i\)
Alice	8	2
Bob	7	10
Carol	6	9

Need \(a=1\) programmer and \(b=2\) artists. Greedy-by-P picks Alice as programmer (8), Bob and Carol as artists (\(10 + 9 = 19\)). Total = 27.

But the optimal: Bob as programmer (7), Alice and Carol as artists (\(2 + 9 = 11\)). Total = 18. Or Carol as programmer (6), Alice and Bob as artists (\(2 + 10 = 12\)). Total = 18.

Greedy-by-P gives 27, optimal is 18. The problem: Alice has the highest \(P_i\), but she's terrible as an artist. Assigning her as programmer "wastes" a spot that a decent all-rounder (Bob) could fill while freeing Alice for a role where she drags down the total.

Instead of asking "who is the best programmer?", ask "who benefits most from being a programmer instead of an artist?"

Deriving the Sort Key

Suppose an optimal assignment has Person 1 as a Programmer and Person 2 as an Artist. What happens if we swap their roles?

Before swap: contribution \(= P_1 + A_2\)
After swap: contribution \(= P_2 + A_1\)

The original assignment is at least as good when:

\[P_1 + A_2 \geq P_2 + A_1\]

Rearranging:

\[P_1 - A_1 \geq P_2 - A_2\]

The quantity \(D_i = P_i - A_i\) measures how much better applicant \(i\) is at programming relative to art. A high \(D_i\) means "programmer-leaning." A low \(D_i\) means "artist-leaning."

Sort applicants by \(D_i = P_i - A_i\) descending. The top portion supplies programmers, the bottom portion supplies artists.

But where exactly do we split? That depends on the actual skill values, not just the differences. We need a sweep.

The Sweep Line Algorithm

After sorting by \(P_i - A_i\) descending, imagine a split point: applicants \(0..s\) are candidates for the programmer pool, applicants \(s+1..n-1\) are candidates for the artist pool.

Here's where almost every first implementation breaks: you might think "just take the first \(a\) from the left and the last \(b\) from the right." But the split point matters. Within the left group, you still need the \(a\) highest \(P_i\) values, not just any \(a\) applicants. Same for the right group and \(A_i\).

For each valid split point \(s\) (where \(s \geq a-1\) and \(n - s - 1 \geq b\)):

From the first \(s+1\) applicants, pick the \(a\) with the highest \(P_i\) values.
From the last \(n - s - 1\) applicants, pick the \(b\) with the highest \(A_i\) values.

We maintain these selections efficiently using min-heaps:

Prefix pass (left to right): maintain a min-heap of size \(a\) tracking the best programming skills seen so far. When the heap exceeds size \(a\), pop the smallest. Record bestProgrammerSums[i] = sum of the heap when it has exactly \(a\) elements.

Suffix pass (right to left): same idea, but for artistic skills with a heap of size \(b\).

Final sweep: for each split point, answer = bestProgrammerSums[s] + bestArtistSums[s+1].

Total complexity: \(O(n \log n)\) for sorting + two heap passes.

Sweep line visualization — applicants sorted by D_i on a number line, with a split point dividing programmer candidates (left) from artist candidates (right), min-heaps maintaining the best selections in each half

Tracing the Algorithm

Example: \(n=5\), \(a=2\) programmers, \(b=2\) artists.

Applicant	\(P_i\)	\(A_i\)	\(D_i = P_i - A_i\)
0	9	1	8
1	7	5	2
2	4	6	-2
3	3	8	-5
4	1	10	-9

Sorted by \(D_i\) descending: already sorted (0, 1, 2, 3, 4).

Prefix pass (best 2 programmers from first i+1):

i	\(P_i\) added	Heap contents (min on top)	Heap size	Pop?	bestProgrammerSums[i]
0	9	{9}	1	No	— (size < 2)
1	7	{7, 9}	2	No	16
2	4	{7, 9} after popping 4	2	Yes	16
3	3	{7, 9} after popping 3	2	Yes	16
4	1	{7, 9} after popping 1	2	Yes	16

Stare at this table. Every time we try to add a weaker programmer, the heap ejects it immediately. The best two programming skills (9 and 7) lock in early and never leave.

Suffix pass (best 2 artists from last n-i):

i	\(A_i\) added	Heap contents (min on top)	Heap size	Pop?	bestArtistSums[i]
4	10	{10}	1	No	— (size < 2)
3	8	{8, 10}	2	No	18
2	6	{8, 10} after popping 6	2	Yes	18
1	5	{8, 10} after popping 5	2	Yes	18
0	1	{8, 10} after popping 1	2	Yes	18

Sweep split points (need \(s \geq 1\) and \(n - s - 1 \geq 2\), so \(s \in \{1, 2\}\)):

Split \(s\)	bestProgrammerSums[\(s\)]	bestArtistSums[\(s+1\)]	Total
1	16	18	34
2	16	18	34

Answer: 34. Let's verify: Programmers are applicants 0 and 1 (skills \(9+7=16\)). Artists are applicants 3 and 4 (skills \(8+10=18\)). No overlap. Total = 34. The brute-force answer across all \(\binom{5}{2} \times \binom{3}{2} = 30\) combinations is also 34.

The Geometric View

Plot each applicant as a point on a 2D plane: X-axis = programming skill, Y-axis = artistic skill.

Running sort by \(P_i - A_i\) descending is geometrically equivalent to dropping a diagonal decision line \(A = P - C\) down the grid. The line starts high (large \(C\), everything is "programmer-leaning") and sweeps downward. At each position:

Below the line: programmer candidates (\(P_i - A_i > C\))
Above the line: artist candidates (\(P_i - A_i < C\))

The sweeping line naturally halts at the exact mathematical threshold that perfectly separates the programmers from the artists. The heaps then select the best \(a\) from below and the best \(b\) from above.

2D scatter plot of applicants with programming skill on X-axis and artistic skill on Y-axis, showing the diagonal decision line A = P - C sweeping downward, separating programmer candidates below from artist candidates above

This geometric view connects directly to the Lagrangian relaxation below — the line's position corresponds to the combined penalty constant \(C = \lambda - \mu\).

Want to go deeper? The LP formulation, Lagrangian relaxation, network flow model, and the geometric theory behind this sweep line are covered in Chapter 8, Lesson 4: "LP and Flow Connections." That lesson explains why the diagonal decision line is mathematically exact, how Lagrangian multipliers shatter the global constraint into independent subproblems, and when this approach breaks down (three roles, non-TUM knapsack).

Try It

Add the sorting lambda to the starter code.

Test case 1:

Input:
5 2 2
9 1
7 5
4 6
3 8
1 10
Output: 34

Before running, predict: after sorting by \(D_i\), which applicants end up in the "programmer zone" and which in the "artist zone"? What are the heap contents at each step?

Test case 2:

Input:
4 1 2
5 5
10 1
1 10
3 3
Output: 25

What would happen if you sorted by \(P_i\) descending instead of \(D_i\)? Would you get 25 or something worse? Try it by hand.

Test case 3:

Input:
3 1 1
1 1
1 1
1 1
Output: 2

All identical. Any assignment of 1 programmer + 1 artist gives \(1+1=2\). What does \(D_i\) equal for every applicant? Does the sort order matter?

Challenge: What happens if \(a + b = n\) (every applicant must be assigned a role)? Does the sweep still work, or does it degenerate to a single split point? Why does this simplify the problem dramatically?

The Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int numApplicants, numProgrammers, numArtists;
    cin >> numApplicants >> numProgrammers >> numArtists;

    vector<array<int, 2>> applicants(numApplicants);
    for (int i = 0; i < numApplicants; i++) {
        cin >> applicants[i][0] >> applicants[i][1];
    }

    auto skillDifferenceCompare = [](const array<int, 2>& x, const array<int, 2>& y) {
        return (x[0] - x[1]) > (y[0] - y[1]);
    };
    sort(applicants.begin(), applicants.end(), skillDifferenceCompare);

    priority_queue<int, vector<int>, greater<int>> programmerHeap;
    vector<long long> bestProgrammerSums(numApplicants, -1);
    long long currentProgrammerSum = 0;

    for (int i = 0; i < numApplicants; i++) {
        programmerHeap.push(applicants[i][0]);
        currentProgrammerSum += applicants[i][0];
        if ((int)programmerHeap.size() > numProgrammers) {
            currentProgrammerSum -= programmerHeap.top();
            programmerHeap.pop();
        }
        if ((int)programmerHeap.size() == numProgrammers) {
            bestProgrammerSums[i] = currentProgrammerSum;
        }
    }

    priority_queue<int, vector<int>, greater<int>> artistHeap;
    vector<long long> bestArtistSums(numApplicants, -1);
    long long currentArtistSum = 0;

    for (int i = numApplicants - 1; i >= 0; i--) {
        artistHeap.push(applicants[i][1]);
        currentArtistSum += applicants[i][1];
        if ((int)artistHeap.size() > numArtists) {
            currentArtistSum -= artistHeap.top();
            artistHeap.pop();
        }
        if ((int)artistHeap.size() == numArtists) {
            bestArtistSums[i] = currentArtistSum;
        }
    }

    long long maxTotalSkill = -1;
    for (int i = numProgrammers - 1; i + numArtists < numApplicants; i++) {
        if (bestProgrammerSums[i] >= 0 && bestArtistSums[i + 1] >= 0) {
            maxTotalSkill = max(maxTotalSkill, bestProgrammerSums[i] + bestArtistSums[i + 1]);
        }
    }

    cout << maxTotalSkill << "\n";
    return 0;
}

Problems

Problem	Link	Difficulty
CSES — Programmers and Artists	cses.fi/problemset/task/2426	Hard
ABC 216G — 01Sequence	atcoder.jp/contests/abc216/tasks/abc216_g	600pts
LC 179 — Largest Number	leetcode.com/problems/largest-number	Medium
LC 871 — Minimum Refueling Stops	leetcode.com/problems/minimum-number-of-refueling-stops	Hard