🔗 Minimum Rectangle

A company that makes business card wallets wants to determine the size of their wallets. They need to make a wallet that can hold business cards of various shapes and sizes, while still being small enough to carry easily. To meet this requirement, the design team surveyed the width and length of every business card.

The table below shows the width and length of 4 business cards.

Since the longest width and length are 80 and 70 respectively, a wallet sized 80 (width) x 70 (length) can hold all the cards. However, if card 2 is rotated to lie horizontally, all the cards can fit into a wallet sized 80 (width) x 50 (length). In this case, the wallet size is 4000 (= 80 x 50).

Given a 2D array sizes containing the width and length of every business card, complete the solution function to return the size of the smallest wallet that can hold all the cards.

• The length of sizes is between 1 and 10,000.
• Each element of sizes is in the form [ w, h ].
• w represents the width of a business card.
• h represents the length of a business card.
• w and h are natural numbers between 1 and 1,000.

Example #1

Same as the problem example.

Example #2

When the cards are rotated appropriately and overlaid, the 3rd card (width: 8, length: 15) is larger than all the other cards. So the wallet size equals the size of the 3rd card, returning 120 (=8 x 15).

Example #3

When the cards are rotated appropriately and overlaid, the smallest wallet size that includes all the cards is 133 (=19 x 7).

In everyday life, business card sizes vary. Of course they seem to follow roughly some standard, but they're not all identical. Also, some cards are portrait-oriented, and some are landscape-oriented.

In this problem, we have a variety of business cards like this, and the goal is to make a wallet that can hold all of them without issue.

Think about how we normally organize business cards. Regardless of size, front/back, or orientation, it's common to align everything along its longer side.

Similarly, we first need to normalize the orientation of the cards in code. Regardless of the given orientation, sort so that the longer of the two lengths comes first.

Then, relatively speaking, they become sorted as [ card's longer side, card's shorter side ].

Afterward, by iterating through with a for loop, we find the largest value among the longer sides and the largest value among the shorter sides, and every card can then be stored without issue.

JAVA
/**
 * Minimum Rectangle class
 *
 * @author RWB
 * @since 2021.12.12 Sun 16:20:39
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param sizes: [int[][]] width and length
	 *
	 * @return [int] answer
	 */
	public int solution(int[][] sizes)
	{
		int w = 0;
		int h = 0;
		
		for (int i = 0; i < sizes.length; i++)
		{
			int a = sizes[i][0];
			int b = sizes[i][1];
			
			// Regardless of orientation, place the longer length in sizes[i][0] and the shorter length in sizes[i][1]
			sizes[i][0] = Math.max(a, b);
			sizes[i][1] = Math.min(a, b);
			
			// Find the maximum of the longer lengths, and the maximum of the shorter lengths
			w = Math.max(w, sizes[i][0]);
			h = Math.max(h, sizes[i][1]);
		}
		
		return w * h;
	}
}

If you prefer, you can simplify this to a form like w = Math.max(w, Math.max(sizes[i][0], sizes[i][1]));.