# Seeds distribution algorithm with complexity better than O(n^3)?

I have included my approach and solution. My solution works fine, however, is unoptimized with O(n^3) complexity

An NGO is running seed distribution program. It has limited quantity of varied quality seeds. In order to get seeds, farmer needs to request number of seeds. Seed distribution happens only on Sunday with goal that maximum farmers gets best quality seeds of same type.

Consider, NGO has following seeds and count (Ordered by quality - Top is highest):

|Quality|Fruit1|Fruit2|Fruit3|
|-------|------|------|------|
|Highest|     3|     3|     1|
|Medium |     2|     0|     0|
|Low    |     4|     0|     0|

Required Seeds:

• Farmer 1: 2
• Farmer 2: 3
• Farmer 3: 1
• Farmer 4: 2
• Farmer 5: 3

Output: Goal is to assign highest quality seeds to maximum farmers.

• Farmer 1: Highest Fruit1
• Farmer 2: Highest - Fruit2
• Farmer 3: Highest - Fruit1
• Farmer 4: Medium - Fruit1
• Farmer 5: Low - Fruit1

Here, farmer 1 and 3 in combination requested for 3 seeds, hence, in combination got highest fruit1.

My approach (Pseudocode)

I have a following domain classes - Farmer, , QualityType, FruitType, Seeds

QualityType has list of FruitType which has list of seeds.

To obtain result, I am doing following:

• Iterate from highest Quality type to lowest.
• nested iterate to fruit type and seeds.
• For any seeds, check if we have farmer1 asking for same number of seeds - either alone or in combination with any one else.
• If not move to farmer two.
• This works however isn't optimized as it has 3 nested loops.

Can you please suggest any algorithm that can simplify it?

• Can you give a farmer two different types (fruit or quality) of seed? Commented Jul 9, 2015 at 14:42
• No, if farmer requirement is more than seed of any type available, code should request him to reduce requirement. Commented Jul 9, 2015 at 14:46
• what happens if 2 farmers ask for 3 seeds each, and you only have 5 available? Commented Jul 9, 2015 at 14:58
• First come, first served Commented Jul 9, 2015 at 15:03