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|
- 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?