Pattern visualizer
Chocolate Distribution Problem
Fairness here is one number: largest packet handed out minus smallest. Sorting turns the search into a much smaller one, because in sorted order the m packets closest in size are always next to each other — reaching past a packet to grab a further one can only stretch the gap. So slide a window of exactly m packets across the sorted list; the difference between its two ends is that group's spread, and the smallest spread seen wins. Animated on: packets = 21, 3, 8, 5, 13, 17, 19, 30 and m = 4 students — hand one packet to each student so the biggest packet given out minus the smallest is as small as possible..
Sort, then slide a fixed window of m packets
8 packets 21, 3, 8, 5, 13, 17, 19, 30 to hand out to 4 students, one packet each. We want the group of 4 where the biggest and smallest packet are as close as possible.
1FUNCTION minSpread(packets, m):2 packets <- SORT(packets)3 best <- INFINITY4 FOR i <- 0 TO LENGTH(packets) - m5 j <- i + m - 16 spread <- packets[j] - packets[i]7 IF spread < best8 best <- spread9 RETURN best
← / → step · space play · Home restart