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.