The Stable Matching Problem (aka SMP or Stable Marriage) is a problem where two equally sized sets need to be matched. Each item in a set has a preference of which item in the opposite set to be matched to.
Take a set of Applicants and a set of Jobs. The number of Applicants and Jobs are equal. Each Applicant has a preference list of all Jobs. Each Job has a preference list of all Applicants.
We desire a stable match of Applicants and Jobs. Stability means that matchings will not change, there is no possibility for an Applicant-Job pairing to change.
We can achieve stability by making sure each Applicant is matched with best Job possible (highest on the preference). This doesn't mean that an Applicant will get the top Job, or even a Job high on their preference list. It means they will the highest Job available to them.
If a Job is desirable to two Applicants, the Job will prefer one Applicant over the other. The Job accepts the better Applicant, and the rejected Applicant must seek the next Job on their preference list.
Running Time
O(n^2)
Data Structures
Preference list for each applicant - ApplicantPref[a,i]
Preference list for each job - JobPref[j,i]
Linked list of available applicants
Ranking array for each Job Ranking[j, i]