All problems

Bakery Batch Planner

Medium · knapsack

A bakery has one oven that can run for hours hours today. The list batches describes the batches you could bake: batches[i] = [hours_needed, profit]. Batches are numbered from 0. You can bake each batch at most once, and the batches you pick must need no more than hours hours in total.

Return the numbers of the batches to bake, in increasing order, so that the total profit is as large as possible.

Several choices can give the same best profit. In that case return the one that comes first when index lists are compared like words: look at the first position where two lists differ, and the list with the smaller batch number there comes first. For example, [0, 3] comes before [1, 2].

If no batch fits in the oven, return an empty list.

Examples

Example 1

Input: batches = [[2, 30], [3, 40], [4, 50]], hours = 5

Output: [0, 1]

Batches 0 and 1 need 5 hours and earn 70. Batch 2 alone earns only 50, and batches 0 and 2 need 6 hours.

Example 2

Input: batches = [[2, 10], [2, 10], [2, 10]], hours = 4

Output: [0, 1]

Any two batches earn 20. Of [0, 1], [0, 2] and [1, 2], the list [0, 1] comes first.

Example 3

Input: batches = [[6, 5]], hours = 3

Output: []

The only batch needs 6 hours, so nothing can be baked.

Constraints