MiddleCodeRareNot answered yet
Total buyer dissatisfaction over nearest available goods
goods holds available product values (unlimited stock of each). Each buyer in needs takes the good nearest to their need; dissatisfaction is abs(need - chosen). Return the total dissatisfaction over all buyers.
Requirements:
- O(n log n) time; beat the O(n*m) brute force.
- Example:
goods=[8,3,5], needs=[5,6]->1.
def total_dissatisfaction(goods, needs):
# your code hereWrite the implementation.
Sort goods once, then for each need binary-search its insertion point with bisect_left and compare the neighbour just below and just above, taking the smaller abs distance. Summing those gives the answer in O((n+m) log n). Brute force — scanning all goods per buyer — is O(n*m). The candidates around the insertion index are the only two that can be nearest.
- ✗Settling for the O(n*m) per-buyer scan instead of binary search
- ✗Checking only one neighbour of the insertion point, missing the closer side
- ✗Pairing sorted lists index-by-index, which ignores unlimited stock
- →Why must you check both neighbours of the
bisect_leftindex? - →How would a two-pointer merge over two sorted lists achieve the same bound?
Contents
Task
Implement total_dissatisfaction: for each buyer pick the nearest good and sum abs(need - chosen) in O(n log n).
Solution
from bisect import bisect_left
def total_dissatisfaction(goods, needs):
goods = sorted(goods)
total = 0
for need in needs:
i = bisect_left(goods, need)
best = float("inf")
if i < len(goods):
best = min(best, abs(goods[i] - need)) # neighbour above
if i > 0:
best = min(best, abs(goods[i - 1] - need)) # neighbour below
total += best
return totalKey points
- Sort goods once;
bisect_leftgives the insertion point in O(log n). - The nearest good is either
goods[i]orgoods[i-1]; check both. - Scanning all goods per buyer would be O(n*m).
Contents
