Difficulty: Easy | Acceptance: 75.30% | Paid: No Topics: Math
You are given the length n and width m of a ship. You are also given the length length and width width of a container. You can rotate the container 90 degrees. Return the maximum number of containers that can be placed on the ship.
- Examples
- Constraints
- Mathematical Calculation
- Dimension Sorting
Examples
Input: n = 3, m = 2, length = 1, width = 2
Output: 3
Explanation:
- Without rotation: (3 // 1) * (2 // 2) = 3 * 1 = 3 containers.
- With rotation: (3 // 2) * (2 // 1) = 1 * 2 = 2 containers.
- The maximum is 3.
Input: n = 4, m = 5, length = 2, width = 3
Output: 2
Explanation:
- Without rotation: (4 // 2) * (5 // 3) = 2 * 1 = 2 containers.
- With rotation: (4 // 3) * (5 // 2) = 1 * 2 = 2 containers.
- The maximum is 2.
Constraints
- 1 <= n <= 1000
- 1 <= w <= 1000
- 1 <= maxWeight <= 10^9
Mathematical Calculation
Intuition Since containers must be placed axis-aligned and can be rotated, there are only two valid orientations to consider. We calculate the number of containers that fit for both orientations and return the maximum.
Steps
- Calculate the number of containers that fit without rotation:
(n // length) * (m // width). - Calculate the number of containers that fit with 90-degree rotation:
(n // width) * (m // length). - Return the maximum of the two values.
class Solution:
def maxContainers(self, n: int, m: int, length: int, width: int) -> int:
# Calculate containers for both orientations
option1 = (n // length) * (m // width)
option2 = (n // width) * (m // length)
# Return the maximum
return max(option1, option2)Complexity
- Time: O(1)
- Space: O(1)
- Notes: This approach is optimal as it performs a constant number of arithmetic operations.
Dimension Sorting
Intuition We can normalize the dimensions of both the ship and the container so that we always align the longest side of the ship with the longest side of the container. This simplifies the calculation to a single orientation check.
Steps
- Determine the maximum and minimum dimensions for the ship:
max_n = max(n, m),min_n = min(n, m). - Determine the maximum and minimum dimensions for the container:
max_l = max(length, width),min_l = min(length, width). - Calculate the result using the aligned dimensions:
(max_n // max_l) * (min_n // min_l).
class Solution:
def maxContainers(self, n: int, m: int, length: int, width: int) -> int:
# Normalize ship dimensions
max_n = max(n, m)
min_n = min(n, m)
# Normalize container dimensions
max_l = max(length, width)
min_l = min(length, width)
# Calculate fit with aligned dimensions
return (max_n // max_l) * (min_n // min_l)Complexity
- Time: O(1)
- Space: O(1)
- Notes: This approach is logically equivalent to the first but uses sorting to explicitly align dimensions.