Stable marriage problem (You CAN always find a stable perfect matching, when nodes aren’t unisex / must be heterosexual)
Have some boys and girls (N boys & N girls)
(constraint: boys can only be paired with girls, and vice versa)
All the boys have ranked preference list of all the girls they like.
Vice Versa. (All the girls have a ranked preference list of the boys)
GOAL: Find perfect matching s.t. there are no rogue couples.

e.g.

Boys
1. CBEAD
2. ABECD
3. DCBAE
4. ACDBE
5. ABDEC
Girls
A. 35214
B. 52143
C. 43512
D. 12345
E. 23415

How solve? Greedy algo (always try 1st. it’ll work a/b 50% of time in life, 50% of time it won’t):
1->C
2->A
3->D
4->B (rogue couple. 4C.)
5->E

Trying to ‘patch’ things up, you create other rogue couples/the orders get all mixed up.
Can NOT require first matching a boy and girl that ‘like eachother best’ and then recurse on that, b/c you don’t know if the base case will exist.

Balcony Serenading Algo. (aka the marriage algorithm, TMA)
Init. cond: preference lists (as above)
A ritual: takes place over several days. Each day split into 3 parts: morning, noon & night.
Each morning, girl comes out to her balcony to check who’s there.
Each boy, goes to balcony of his fav girl who’s still on his list, hasn’t been crossed off (initially, every girl is still on his list so he just goes to his 1st favorite) off and serenades her.
If he has nobody left, he just stays home & does homework, no serenading.
At noon, girls who have at least 1 suitor, picks her favorite, says “maybe I’ll marry you, come back tomorrow.” Banishes the other lower priority boys.
At night, the boys who heard “No”, he crosses her off his list, goes to his next priority tomorrow.
Recurse the algo.

If ever find a condition in which every girl has at most 1 suitor (i.e. no balconies have > 1 suitor), then the termination condition is met, the boys and girls marry whoever is there.

Girls         Day1 Day2 Day3 Day4 (Who came to balcony? Girl picks from them one to tell “hang around / come back tmrw”)
A	      2,4,5    5        5	5
B		      2	   2,1	2
C	         1      1,4      4	4
D	         3       3        3	3
E				1