Minimum-Cost Padded Batch Partition

Problem

Stably sort requests by increasing token length (ties preserve original index), then partition this sorted order into contiguous batches of at most max_batch_size. A batch costs launch_overhead + batch_count * maximum_length_in_batch. Minimize total cost.

Among equal total costs, prefer fewer batches; if still tied, choose the lexicographically smaller sequence of batch sizes from first to last (a smaller first differing batch wins). Return {"cost": minimum integer cost, "batches": lists of original request indices in execution order}. Empty input has cost 0 and no batches. This additive padding/launch model is specified for optimization practice, not a measured GPU latency model.

def minimum_cost_batches(lengths, max_batch_size, launch_overhead):

Constraints

• lengths contains 0..64 positive integers ≤128; 1 ≤ max_batch_size ≤16.
• launch_overhead is a nonnegative integer ≤1000; preserve all request indices exactly once.
• Inputs satisfy these constraints; invalid-input handling is not graded. Use only Python standard library and NumPy.

Examples

Arguments: [
  [
    1,
    2,
    10
  ],
  3,
  0
]
Expected result: {
  "cost": 13,
  "batches": [
    [
      0
    ],
    [
      1
    ],
    [
      2
    ]
  ]
}

Arguments: [
  [
    1,
    2,
    10
  ],
  3,
  20
]
Expected result: {
  "cost": 50,
  "batches": [
    [
      0,
      1,
      2
    ]
  ]
}