All problems

Seed Packet Count

Medium · greedy

A garden shop sells seeds in paper packets. The list widths holds the width of every seed that needs packing, as a whole number of tenths of a millimetre.

Seeds of very different sizes do not sow well together, so every packet must follow two rules:

• it holds at most capacity seeds, and
• the widest and the narrowest seed in it differ by at most spread.

Every seed goes into exactly one packet. Return the fewest packets needed.

Examples

Example 1

Input: widths = [3, 9, 4, 10, 5], spread = 2, capacity = 3

Output: 2

Widths 3, 4 and 5 fill one packet. Widths 9 and 10 share a second one.

Example 2

Input: widths = [7, 7, 7, 7, 7], spread = 0, capacity = 2

Output: 3

Spread is not a problem, but a packet holds only two seeds, so five seeds need three packets.

Example 3

Input: widths = [1, 50, 100], spread = 100, capacity = 5

Output: 1

Constraints

• 1 <= len(widths) <= 10^4
• 1 <= widths[i] <= 100
• 0 <= spread <= 100
• 1 <= capacity <= 10^4