Good Samaritan

TIP102 Unit 1 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Arrays, Sorting

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• The function 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

P-lan

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

• Not handling the case where meals can be split among multiple boxes.
• Not breaking out of the loop once all meals are distributed.

I-mplement

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