(We might later come back to this decision.) After Anna, we get to Barbara.
Unfortunately, her only potential partner Frank is already taken and so we cannot assign her any partner.
Suppose you’re in charge of organizing the Valentine’s day activity for your high school class: a date night.
All interested singles send you their (secret) list of the people they fancy and would find acceptable as a Valentine’s date.
My goal in this article is to teach you the algorithm for finding the best dating schedule.
It is a structured series of steps that is guaranteed to lead to an optimal solution.
Even if you worked at the speed up a modern computer, checking a million different schedule every second, it would take you a year to go through that many possibilities.
It’s a bit like an IKEA manual for assembling a piece of furniture: it gives step-by-step instructions on how to proceed.
But while an IKEA manual works only to build one particular type of furniture (bookcase Billy) from one particular packet of materials, the algorithm works for any input (your classmate's preference lists), and always produces a correct output (a best-possible dating schedule).
Luckily, there is a much better approach to find the best schedule, based on clever mathematical insights.
To use it for a class with 15 boys and girls, you only need to consider 15 schedules throughout the process, rather than the billions of possibilities in the brute-force solution!