Minimum Document Padding for GPU Buckets
Learn this problem
AmazonNEW GRADPHONE SCREENProblem statement
You have lengths.length documents that must be split into exactly groups non-empty GPU batches. Every document in one batch is padded to the length of the longest document in that batch.
If a batch contains document lengths x1, x2, ..., xm and its maximum is M, that batch adds m * M - (x1 + x2 + ... + xm) padding units.
Return the minimum total padding over all batches. You may reorder documents before batching. Documents with similar lengths can therefore be grouped together.
Function
minimumPadding(lengths: int[], groups: int) → longExamples
Example 1
lengths = [2,3,7,8]groups = 2return = 2After sorting, use batches [2,3] and [7,8]. Each batch adds one padding unit, for a total of 2.
Example 2
lengths = [5,5,5]groups = 2return = 0All documents already have equal length, so every valid two-batch split uses zero padding.
Example 3
lengths = [1,4,7]groups = 1return = 9The only batch pads all three documents to length 7, adding (7 - 1) + (7 - 4) + (7 - 7) = 9 units.
Constraints
1 <= groups <= lengths.length <= 200.1 <= lengths[i] <= 10^6.- Every batch must contain at least one document.