Implement Optimal Bucket Batching

You are given an array lengths of K document lengths and an integer G representing the number of available GPUs. A batch is assigned to one GPU, and every document in the same batch is padded to the maximum document length in that batch. Reordering documents is allowed.

Choose up to G non-empty batches, with unused GPUs allowed, to minimize the total padding waste:

sum over batches of (batch_size * max_length_in_batch - sum_of_lengths_in_batch)

Return both the minimum padding waste and one optimal partition of the documents into batches. If K = 0, return zero waste and an empty partition. If G >= K, the optimal solution may place each document in its own batch, producing zero padding waste.

Implement an efficient algorithm and explain its time and space complexity.