[Solved] Apple Redistribution into Boxes leetcode C++,JAVA, Python

You are given an array apple of size n and an array capacity of size m.

There are n packs where the ith pack contains apple[i] apples. There are m boxes as well, and the ith box has a capacity of capacity[i] apples.

Return the minimum number of boxes you need to select to redistribute these n packs of apples into boxes.

Note that, apples from the same pack can be distributed into different boxes.

Example 1:Input: apple = [1,3,2], capacity = [4,3,1,5,2]

Output: 2 Explanation: We will use boxes with capacities 4 and 5. It is possible to distribute the apples as the total capacity is greater than or equal to the total number of apples.

Example 2:Input: apple = [5,5,5], capacity = [2,4,2,7]

Output: 4 Explanation: We will need to use all the boxes.

Constraints:

• 1 <= n == apple.length <= 50
• 1 <= m == capacity.length <= 50
• 1 <= apple[i], capacity[i] <= 50
• The input is generated such that it’s possible to redistribute packs of apples into boxes.

Solution

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i=0;i<capacity.length;i++){
            pq.add(capacity[i]);
        }
        int sum =0;
        
        for(int i=0;i<apple.length;i++){
            sum = sum + apple[i];
            
        }
        
        int count =0;
        while(!pq.isEmpty()){
            int k = pq.poll();
            if(sum>k){
                count++;
                sum = sum - k;
                
            }
            else{
                count++;
                return count;
            }
            
        }
       
        // System.out.println(pq);
        return count;
        
        
    }
}

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int minimumBoxes(int[] apple, int[] capacity) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < capacity.length; i++) {
            pq.add(capacity[i]);
        }
        
        int sum = 0;
        
        for (int i = 0; i < apple.length; i++) {
            sum = sum + apple[i];
        }
        
        int count = 0;
        while (!pq.isEmpty()) {
            int k = pq.poll();
            if (sum > k) {
                count++;
                sum = sum - k;
            } else {
                count++;
                return count;
            }
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        // Example usage
        Solution solution = new Solution();
        int[] apple = {10, 20, 30};
        int[] capacity = {20, 30, 40};
        System.out.println(solution.minimumBoxes(apple, capacity)); // Output should be 3
    }
}

import heapq

class Solution:
    def minimumBoxes(self, apple, capacity):
        pq = [-c for c in capacity]
        heapq.heapify(pq)
        
        total_apples = sum(apple)
        
        count = 0
        while pq:
            k = -heapq.heappop(pq)
            if total_apples > k:
                count += 1
                total_apples -= k
            else:
                count += 1
                return count
        return count

# Example usage
solution = Solution()
apple = [10, 20, 30]
capacity = [20, 30, 40]
print(solution.minimumBoxes(apple, capacity))  # Output should be 3