Fairest Way to Hand Out Packets

EasyArraysSortingSliding window223 tests

You have n packets. packets[i] is the number of sweets in packet i. There are m students, and m <= n.

Give exactly one packet to each student. Each packet can go to at most one student, and some packets may stay unused.

The spread of a choice is the largest packet given out minus the smallest packet given out. Return the smallest possible spread.

Note

If m is 1, one packet has the same largest and smallest value, so the spread is 0.

Hint: sort the packets first. Then think about which groups of m packets you really need to check.

Examples

Example 1

Input:: [12,4,30,9,18,25,7], 3
Output:: 5

Sorted, the packets are 4, 7, 9, 12, 18, 25, 30. The packets 4, 7 and 9 give a spread of 9 - 4 = 5. No group of three does better.

Example 2

Input:: [40,41,3,90], 2
Output:: 1

Give out 40 and 41. The spread is 41 - 40 = 1.

Example 3

Input:: [15,2,8], 3
Output:: 13

There are three students and three packets, so every packet is used. The spread is 15 - 2 = 13.

Constraints

1 <= m <= n <= 30
1 <= packets[i] <= 500

Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.