CODEWITHSUNDEEP
algorithmsortingsetbipartite
Phoenix1237
Phoenix1237

Reputation: 35

Algorithm to pair 2 objects within an allowed weight range?

I am looking to find a way to pair 2 objects that are +- a certain weight with each other, to create the most pairs possible. Example: I have 100 of said objects, all ranging from 1-100 pounds and are allowed to be paired +-5 pounds off their current weight. How could I most efficiently create the most pairs. I have a unique identifier and their weight and I am comparing them all to the same set. I looked into some algorithms (Hungarian) but not sure which I could apply to this issue and how, so any help would be great thanks!

Upvotes: 0

Views: 81

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65506

Sort the objects by weight. Repeat until no objects remain: if the lightest two are within five pounds, pair and remove them. Otherwise, remove the lightest.

This greedy algorithm can be proved optimal.

Upvotes: 1

Related Questions