Complete All Baking Batches
A bakery has several ovens and batches that must be baked. Each oven starts with a given heat level, and each batch requires a minimum heat level.
An oven can bake a batch when its current heat is at least the required heat. After baking one batch, the oven's heat becomes half of its current value, rounded down.
Determine whether every batch can be completed in each schedule.
Implement the following method:
List<Integer> canBakeAllBatches( List<String> ovenSchedules, List<String> batchSchedules )
- Each value in
ovenSchedules contains the starting heat levels of the ovens for one schedule.
- Each value in
batchSchedules contains the required heat levels of the batches for the corresponding schedule.
- The numbers inside each string are separated by commas.
- Return one result for each schedule in the same order as the input.
Baking Rules
- Batches may be completed in any order.
- Any batch may be assigned to any oven.
- The same oven may bake multiple batches.
- An oven with current heat
h can bake a batch requiring heat r only when h >= r.
- After baking the batch, that oven's heat becomes
floor(h / 2).
- An oven cannot be reheated during a schedule.
- All schedules are independent.
- The order of values inside a schedule does not affect the result.
Return Values
- Return
1 for a schedule if every batch can be completed.
- Return
0 for a schedule if at least one batch cannot be completed.
- The returned list contains results in the same order as the schedules.
Constraints
1 <= ovenSchedules.size() = batchSchedules.size() <= 100 - Each schedule contains between
1 and 100,000 ovens.
- Each schedule contains between
1 and 100,000 batches.
- Every oven heat level is between
1 and 1,000,000,000.
- Every batch heat requirement is between
1 and 1,000,000,000.
- Every input string contains positive integers separated by single commas, without spaces.
- The total number of ovens and batches across all schedules does not exceed
200,000.
Examples
Example 1
canBakeAllBatches( ovenSchedules = List.of("24,13", "16,10"), batchSchedules = List.of("12,11,6,5,3", "15,10,8,5,5") )
Output: List.of(1, 0)
In the first schedule, the ovens can complete every batch.
In the second schedule, after completing the batches requiring heat 15, 10, 8, and 5, the hottest remaining oven has heat 4. Therefore, the final batch requiring heat 5 cannot be completed.
Example 2
canBakeAllBatches( ovenSchedules = List.of("21", "11,7,4"), batchSchedules = List.of("20,10,5,2", "11,7,5,4,3") )
Output: List.of(1, 1)
In the first schedule, the oven's heat changes from 21 to 10, then to 5, then to 2. Therefore, it can complete all four batches.
In the second schedule, assigning each batch to the hottest available oven allows all five batches to be completed.
Example 3
canBakeAllBatches( ovenSchedules = List.of("7,5", "30,8"), batchSchedules = List.of("8", "15,14,7,4") )
Output: List.of(0, 1)
In the first schedule, neither oven reaches the required heat of 8.
In the second schedule, the batches can be completed using oven heat levels 30, 15, 8, and 7.