Couples - Greedy Approach

The greedy approach: process pairs from left to right. For positions $(0,1)$, $(2,3)$, etc., check if a couple sits there.

If not, swap to fix it. For person at position $2i$, their partner is either $person \oplus 1$ (XOR flips the last bit).

If the person at $2i+1$ is not the partner, find the partner elsewhere and swap. Each swap fixes exactly one couple.

You never need to undo a fix.

This greedy approach gives minimum swaps.