TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
Q: What is the input to the function?
meals
, which contains the number of meals in each pack, and capacity
, which contains the maximum capacity of each box.Q: What is the expected output of the function?
Q: Can meals from the same pack be split across multiple boxes?
Q: What should the function return if there are more meals than the total capacity of all boxes?
Q: Are the input arrays guaranteed to have the same length?
capacity
will have enough boxes to hold all the meals, even if they are distributed.minimum_boxes()
should take in two lists, meals and capacity, and return the minimum number of boxes needed to hold all the meals using the least number of boxes possible.HAPPY CASE
Input: meals = [1,3,2], capacity = [4,3,1,5,2]
Expected Output: 2
Input: meals = [5,5,5], capacity = [2,4,2,7]
Expected Output: 4
EDGE CASE
Input: meals = [10], capacity = [5,5,5,5]
Expected Output: 2
Input: meals = [1,1,1], capacity = [1,1,1]
Expected Output: 3
Plan the solution with appropriate visualizations and pseudocode.
General Idea: To minimize the number of boxes used, sort the boxes by their capacities in descending order and start filling the largest boxes first.
1. Sort the `capacity` array in descending order.
2. Calculate the total number of meals by summing up the `meals` array.
3. Initialize a counter `box_count` to 0.
4. Iterate through the sorted `capacity` array and subtract each capacity from the total number of meals until all meals are distributed.
a. For each box used, increment `box_count`.
b. If the total meals are less than or equal to 0, break the loop.
5. Return `box_count`
⚠️ Common Mistakes
Implement the code to solve the algorithm.
def minimum_boxes(meals, capacity):
# Sort the capacity array in descending order
capacity.sort(reverse=True)
# Calculate the total number of meals
total_meals = sum(meals)
# Initialize the counter for the number of boxes used
box_count = 0
# Distribute the meals using the largest boxes first
for cap in capacity:
total_meals -= cap
box_count += 1
if total_meals <= 0:
break
return box_count