Stable Marriage problem
Given n men and n women who have ranked the other group in order of preference, marry the men with the women so that no two people would rather be with each other than with their spouses.
The Gale-Shapley algorithm solves this in O(n2) time.