LeetCode 1889: Minimum Space Wasted From Packaging Solution
Master LeetCode problem 1889 (Minimum Space Wasted From Packaging), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
1889. Minimum Space Wasted From Packaging
Problem Explanation
Explanation
To solve this problem, we need to find the minimum wasted space by selecting boxes optimally from a single supplier. The key idea is to sort the packages and boxes in ascending order. Then, for each package, we try to find the smallest box that can accommodate it while minimizing the wasted space. We keep track of the total wasted space and return the minimum total wasted space.
- Sort the packages and boxes in ascending order.
- Iterate over each package and find the smallest box that can accommodate it.
- Calculate the wasted space for each package and update the total wasted space.
- Return the minimum total wasted space.
Time complexity: O(n log n + m log m + n log m) where n is the number of packages and m is the number of boxes.
Space complexity: O(1)
Solution Code
class Solution {
public int minWastedSpace(int[] packages, int[][] boxes) {
int mod = (int)1e9 + 7;
Arrays.sort(packages);
long totalWastedSpace = Long.MAX_VALUE;
for (int[] boxSizes : boxes) {
Arrays.sort(boxSizes);
if (boxSizes[boxSizes.length - 1] < packages[packages.length - 1]) continue;
long currentWastedSpace = 0;
int boxIdx = 0;
for (int packageSize : packages) {
int idx = Arrays.binarySearch(boxSizes, packageSize);
if (idx < 0) idx = -idx - 1;
if (idx >= boxSizes.length) {
currentWastedSpace = Long.MAX_VALUE;
break;
}
currentWastedSpace += boxSizes[idx] - packageSize;
}
totalWastedSpace = Math.min(totalWastedSpace, currentWastedSpace);
}
return totalWastedSpace == Long.MAX_VALUE ? -1 : (int)(totalWastedSpace % mod);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 1889 (Minimum Space Wasted From Packaging)?
This page provides optimized solutions for LeetCode problem 1889 (Minimum Space Wasted From Packaging) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 1889 (Minimum Space Wasted From Packaging)?
The time complexity for LeetCode 1889 (Minimum Space Wasted From Packaging) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 1889 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1889 in Java, C++, or Python.