8000 Add 3074_apple_redistribution_into_boxes · m3xw3ll/LeetCode@58bb4f0 · GitHub
[go: up one dir, main page]
Skip to content

Commit 58bb4f0

Browse files
m3xw3llm3xw3ll
committed
Add 3074_apple_redistribution_into_boxes
1 parent 8225829 commit 58bb4f0

File tree

3 files changed

+60
-0
lines changed

3 files changed

+60
-0
lines changed

‎Algorithms/3074_apple_redistribution_into_boxes.md

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
# [Apple Redistribution into Boxes](https://leetcode.com/problems/apple-redistribution-into-boxes/description/)
2+
3+
You are given an array apple of size n and an array capacity of size m.
4+
5+
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.
6+
7+
Return the minimum number of boxes you need to select to redistribute these n packs of apples into boxes.
8+
9+
Note that, apples from the same pack can be distributed into different boxes.
10+
11+
Example 1:
12+
```
13+
Input: apple = [1,3,2], capacity = [4,3,1,5,2]
14+
Output: 2
15+
Explanation: We will use boxes with capacities 4 and 5.
16+
It is possible to distribute the apples as the total capacity is greater than or equal to the total number of apples.
17+
```
18+
Example 2:
19+
```
20+
Input: apple = [5,5,5], capacity = [2,4,2,7]
21+
Output: 4
22+
Explanation: We will need to use all the boxes.
23+
```
24+
Solution
25+
```python
26+
class Solution:
27+
def minimumBoxes(self, apple: List[int], capacity: List[int]) -> int:
28+
apple_sum = sum(apple)
29+
cnt = 0
30+
capacity = [-c for c in capacity]
31+
heapq.heapify(capacity)
32+
33+
while apple_sum > 0:
34+
max_capa = heapq.heappop(capacity)
35+
cnt += 1
36+
apple_sum -= -max_capa
37+
38+
return cnt
39+
40+
```
41+

‎Algorithms/snippets/3074_apple_redistribution_into_boxes.py

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
import heapq
2+
3+
4+
def minimum_boxes(apple, capacity):
5+
apple_sum = sum(apple)
6+
cnt = 0
7+
capacity = [-c for c in capacity]
8+
heapq.heapify(capacity)
9+
10+
while apple_sum > 0:
11+
max_capa = heapq.heappop(capacity)
12+
cnt += 1
13+
apple_sum -= -max_capa
14+
15+
return cnt
16+
17+
18+
print(minimum_boxes(apple = [5,5,5], capacity = [2,4,2,7]))

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -753,6 +753,7 @@ To search for a specific problem please use ```STRG + F``` to search for.
753753
| 3005 | [Count Elements With Maximum Frequency](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3005_count_elements_with_maximum_frequency.md)
754754
| 3065 | [Minimum Operations to Exceed Threshold Value I](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3065_minimum_operations_to_exceed_threshold_value_one.md)
755755
| 3069 | [Distribute Elements Into Two Arrays I](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3069_distribute_elements_into_two_arrays_one.md)
756+
| 3074 | [Apple Redistribution into Boxes](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3074_apple_redistribution_into_boxes.md)
756757
| 3079 | [Find the Sum of Encrypted Integers](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3079_find_the_sum_of_encrypted_integers.md)
757758
| 3099 | [Harshad Number](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3099_harshad_number.md)
758759
| 3110 | [Score of a String](https://github.com/m3xw3ll/LeetCode/blob/master/Algorithms/3110_score_of_a_string.md)

0 commit comments

Comments
 (0)
0