Good Samaritan - codepath/compsci_guides GitHub Wiki

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.

  • Q: What is the input to the function?

    • A: The input consists of two arrays: 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?

    • A: The function should return the minimum number of boxes needed to redistribute all the meals.

  • Q: Can meals from the same pack be split across multiple boxes?

    • A: Yes, meals from the same pack can be distributed into different boxes.

  • Q: What should the function return if there are more meals than the total capacity of all boxes?

    • A: The problem assumes that the total capacity is sufficient to hold all the meals, so the function should return a valid number of boxes in this context.

  • Q: Are the input arrays guaranteed to have the same length?

    • A: The problem does not specify that the arrays must have the same length, but typically capacity will have enough boxes to hold all the meals, even if they are distributed.

P-lan

  • 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