Back to questions
MiddleCodeRare
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
