Timeline for I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2017 at 12:16 | vote | accept | Edza | ||
| Nov 6, 2017 at 22:44 | answer | added | gnasher729 | timeline score: 1 | |
| Nov 6, 2017 at 9:28 | comment | added | Raphael | The "standard" problem is called "marriage problem". | |
| Nov 6, 2017 at 9:28 | history | edited | Raphael |
edited tags
|
|
| Nov 6, 2017 at 9:21 | comment | added | Yuval Filmus | In mathematics, when we are not sure of a claim we try to prove or disprove it. | |
| Nov 6, 2017 at 8:17 | comment | added | Edza | Thanks for the reply. :) So take the most attractive girl. Assign her to the boy who will take her, but has the least wiggle room. Then take next most attractive girl and again assign to the boy who will take her, but has the least wiggle room? And so on? Are you sure this will guarantee there is no other assignment with more pairs on the dance floor? | |
| Nov 6, 2017 at 8:10 | comment | added | gnasher729 | Did you try sorting plus greedy assignment? Most attractive girl matched with a boy who would invite her, with the highest lower bound etc. | |
| Nov 6, 2017 at 8:03 | history | asked | Edza | CC BY-SA 3.0 |