Pair People: Match Participants into Compatible Pairs to Maximize Overall Compatibility Score

Question

## Problem

You have `2n` people. Each pair `(i, j)` has a compatibility score `score[i][j]`. Pair all people into `n` non-overlapping pairs to maximize the total compatibility score.

```python
def pair_people(scores: list[list[int]]) -> tuple[int, list[tuple[int,int]]]:
    # Returns (max_score, list_of_pairs)
    pass
```

**Example:**
```
scores (4 people) =
[[0, 6, 2, 4],
 [6, 0, 3, 5],
 [2, 3, 0, 7],
 [4, 5, 7, 0]]
Best pairing: (0,1) score=6, (2,3) score=7 -> total 13
output -> (13, [(0,1),(2,3)])
```

## Approach

Bitmask DP: `dp[mask]` = max score when people in `mask` are already paired. Transition: take the lowest unmatched person, try pairing with every other unmatched person. O(n * 2^(2n)).

## Follow-ups
1. For `2n = 20`, bitmask DP is feasible. What about `2n = 1000`? Discuss approximation algorithms.
2. Some pairs are incompatible (score = -inf). How does that affect your bitmask transitions?
3. This is equivalent to maximum weight matching in a general graph. Name the classical algorithm that solves it in polynomial time.
4. If scores are symmetric and all positive, does greedy (always pick the highest remaining score) give the optimal answer? Provide a counterexample if not.

Pair People: Match Participants into Compatible Pairs to Maximize Overall Compatibility Score

Question Details

Full Details

Topics

More from Square/Block