Problem Statement
Given a rectangular object and several boxes (in this problem, we ignore the height of the box, so a box only has two dimensions) of different sizes, you want to find the box with the smallest area which is large enough to contain the object. When putting the object in the box, it's sides must be parallel with the sides of the box. Thus, you may only rotate the object 0, 90, 180 or 270 degrees (although for obvious reasons you only need to consider rotating with 0 and 90 degrees).
Create a class ObjectPacking which contains the method smallBox which takes an
Definition
- Class:
- ObjectPacking
- Method:
- smallBox
- Parameters:
- int, int, int[], int[]
- Returns:
- int
- Method signature:
- int smallBox(int objWidth, int objLength, int[] boxWidth, int[] boxLength)
- (be sure your method is public)
Notes
- There doesn't have to be any gap between the sides of an object and the sides of the box. Thus, an object with width 5 and length 7 will fit in a box with width 7 and length 5.
- Return -1 if there is no box big enough to contain the object (see example 1).
Constraints
- objWidth will be between 1 and 1000, inclusive.
- objLength will be between 1 and 1000, inclusive.
- boxWidth will contain between 1 and 50 elements, inclusive.
- boxLength will contain between 1 and 50 elements, inclusive.
- boxWidth will contain the same number of elements as boxLength.
- Each element in boxWidth will be between 1 and 1000, inclusive.
- Each element in boxLength will be between 1 and 1000, inclusive.
Examples
7
3
{3}
{7}
Returns: 21
By rotating the object 90 degrees we can precisely fit it into the only box in the list, so the method should return 21 (7*3).
5
8
{6,9,3}
{7,4,5}
Returns: -1
The object can't fit in any of the boxes, no matter if we rotate it or not. The method should thus return -1.
17
5
{19,10,12,40}
{12,20,15,5}
Returns: 200
The object will fit in box 0, 1 and 3. The area of box 1 and 3 are 200 while the area of box 0 is 228, so the method should return 200.
20
44
{36,42,18,37,33,5,30,10,29,9,11,16,48,50,34,44,33,12,31,41}
{42,45,46,24,23,21,21,8,26,25,48,12,10,45,18,6,12,22,42,45}
Returns: 1845
1
10
{9,1,10}
{10,6,4}
Returns: 40
5
4
{2,3,3,3,3}
{2,7,7,4,2}
Returns: -1
3
3
{2,3,3,3,2}
{3,1,3,3,2}
Returns: 9
2
2
{2,2,1,4,4,3,2,4,4,4}
{1,1,2,3,2,4,3,3,2,3}
Returns: 6
8
6
{8,6,2,1,4,3,5,7,1,3,4,3,7,7,7}
{4,5,5,4,2,3,4,7,8,5,1,7,7,1,1}
Returns: -1
6
4
{9,1,4,7,1,7,5,4,5,10,4,1,1,9,9,1,4,9,5,1}
{9,1,2,2,1,8,4,4,8,2,1,5,5,3,1,3,5,3,9,1}
Returns: 40
34
23
{14,38,49,48,31,22,34,34,1,8,33,9,33,9,2,5,46,29,39,31,33,2,36,45,28}
{4,21,36,20,44,4,6,38,50,37,36,22,4,9,36,49,16,40,36,1,15,42,17,37,8}
Returns: 1160
2
41
{2,29,39,47,13,8,44,13,8,32,36,33,41,4,15,34,14,27,43,40,50,31,35,2,27,38,19,40,46,47}
{39,37,44,47,26,25,23,5,25,43,28,5,36,18,40,18,37,21,26,27,19,49,5,19,13,42,38,45,41,5}
Returns: 235
37
11
{41,19,33,58,33,59,50,30,22,57,11,5,10,18,26,38,15,41,55,41,60,51,25,60,28,27,3,36,53,55,5,58,47,30,1,46,42,14,60,50,38,39,41,36,30}
{37,35,50,31,26,37,46,59,58,2,43,38,49,23,36,10,33,49,8,54,57,52,33,53,47,23,27,6,31,21,36,21,36,32,45,54,28,40,8,55,39,17,46,17,45}
Returns: 473
36
51
{49,38,3,39,35,5,9,8,12,31,14,48,65,4,19,57,63,60,39,20,38,10,61,46,7,39,2,38,6,13,13,36,64,53,30}
{32,61,26,68,59,48,61,9,22,36,23,51,41,12,17,68,4,10,39,48,61,40,69,46,43,15,28,66,25,66,41,45,30,61,16}
Returns: 2318
25
19
{26,49,61,37,25,67,1,73,38,27,27,26,70,49,23,23,33,67,7,69,4,1,17,17,28,50,37,44,21,71,7,14,9,77,7}
{2,11,33,63,52,58,61,74,13,49,67,50,27,79,43,2,26,35,34,8,9,3,12,6,75,10,46,36,21,63,20,73,18,69,18}
Returns: 858
34
67
{22,39,50,48,88,29,80,90,34,22,72,13,33,12,79,31,2,74,15,69,20,12,15,9,57,23,4,40,68,77,30,82,15,61,7,78,35,15,53,47}
{51,13,30,67,16,10,43,2,3,81,88,67,23,76,38,47,89,90,17,59,25,27,3,8,88,34,77,16,85,1,90,80,36,9,21,63,4,50,53,90}
Returns: 3002
68
57
{81,69,24,48,50,23,56,27,59,68,97,75,32,84,90,4,32,18,67,50,10,12,72,88,76,22,18,46,43,26,19,98,95,36,55,7,73,21,65,63}
{48,80,93,59,17,2,15,66,74,30,74,60,34,21,54,69,14,67,29,26,43,92,71,54,100,85,36,47,88,37,42,25,39,39,46,77,67,39,37,60}
Returns: 4366
38
177
{19,58,13,98,130,7,115,106,168,191,200,147,37,132,53,184,1,66,72,9,177,191,171,44,27,154,26,87,125,14,145,66,172,189,24,38,129,25,8,28}
{83,196,51,37,149,121,180,86,100,136,65,94,168,180,6,137,185,99,70,200,147,98,7,134,56,120,86,198,70,52,88,80,74,78,17,86,151,47,92,168}
Returns: 11368
157
297
{9,198,103,99,62,243,27,184,25,215,103,271,195,279,116,111,22,65,176,120,145,270,70,48,226,185,135,180,60,202,223,86,201,190,145,217,32,80,252,241}
{219,112,110,14,229,192,46,153,275,90,57,179,250,38,258,253,56,282,63,226,151,205,194,214,63,2,237,48,103,115,83,282,108,17,189,247,184,6,147,276}
Returns: -1
76
265
{247,339,240,348,242,279,387,310,34,38,253,396,352,275,378,190,291,113,80,30,313,302,217,5,176,65,243,73,42,190,149,354,78,344,114,148,87,184,343,206,201,317,387,36,92}
{154,28,168,191,262,263,311,221,49,397,97,313,284,297,262,121,80,114,255,100,355,111,230,94,319,284,235,298,385,379,78,237,294,108,360,256,368,13,202,184,73,170,128,147,165}
Returns: 22932
446
85
{385,228,29,450,122,215,46,389,343,409,56,468,58,423,41,217,11,460,84,189,181,281,116,461,327,296,452,466,225,130,427,274,307,245,182,179,291,187,87,18,369,342,394,231,426}
{189,92,227,268,94,434,228,241,24,403,289,246,466,355,414,37,251,297,396,375,59,70,165,126,475,467,385,148,119,242,473,39,328,347,483,316,400,472,57,344,428,466,371,171,275}
Returns: 58086
579
295
{4,298,374,398,314,59,102,578,346,347,381,380,236,494,123,32,522,536,336,268,391,221,365,439,26,386,56,163,142,348,116,158,95,221,441,169,568,565,458,525,178,204,45,380,443}
{356,300,430,283,134,344,460,425,187,32,184,89,357,361,289,271,136,363,18,64,285,473,33,390,429,158,134,199,310,50,444,567,569,167,169,71,393,300,458,372,280,464,17,233,30}
Returns: -1
483
73
{261,9,508,400,434,587,118,293,410,456,209,465,72,666,667,75,501,607,444,359,69,40,562,474,76,607,569,500,190,606,631,262,312,399,420,389,202,94,22,196,455,292,103,272,146,199,552,503,62,66}
{459,124,692,522,7,77,558,628,473,515,472,165,683,225,469,222,693,412,281,175,167,483,689,286,87,331,386,400,583,621,63,196,196,426,425,86,569,186,267,661,186,107,6,170,343,539,67,232,432,674}
Returns: 45199
54
793
{398,598,597,449,466,23,177,672,119,179,712,189,678,562,630,602,69,207,48,169,537,171,709,230,427,639,325,493,724,94,509,530,641,300,389,720,405,149,165,209,422,17,110,718,533,426,631,519,629,398}
{694,540,450,499,439,148,123,396,299,21,512,399,517,483,421,90,764,495,273,349,419,90,324,718,142,613,84,450,617,184,458,551,430,217,197,595,402,746,422,121,389,203,397,546,653,70,333,602,228,105}
Returns: -1
9
3
{9,8,2,10,7,6,3,1,1,5,7,1,7,5,1,7,10,10,10,9,5,1,8,6,6,8,10,10,9,2,6,4,10,7,9,10,3,5,7,5,2,9,1,5,10,9,1,6,8,3}
{2,9,5,4,9,7,5,10,1,10,8,2,8,6,7,2,10,1,4,8,7,3,2,2,6,7,5,9,8,2,9,8,3,6,2,9,4,5,3,9,2,1,4,7,8,9,9,1,5,8}
Returns: 30
18
11
{7,9,11,19,7,2,13,7,10,8,19,13,14,13,14,4,8,18,4,19,3,11,17,12,17,20,18,3,12,20,3,15,18,10,8,1,18,11,8,20,11,4,8,2,16,4,10,12,14,5}
{17,13,12,11,12,8,13,20,5,4,19,15,10,7,1,20,1,12,16,13,1,11,8,14,12,19,3,19,2,15,16,1,17,16,13,10,6,12,18,9,15,6,6,3,18,10,12,2,11,7}
Returns: 209
43
881
{226,579,775,300,179,494,749,377,785,374,517,386,293,605,555,760,759,854,556,539,272,30,406,191,176,749,342,79,89,170,512,719,447,455,78,530,16,456,400,686,409,466,519,459,753,228,89,650,261,509}
{65,321,67,754,652,338,805,83,848,334,95,18,733,200,176,474,606,810,206,450,727,855,396,378,406,130,184,450,333,563,447,708,650,695,639,665,519,12,732,337,847,344,531,45,121,379,459,343,519,863}
Returns: -1
462
101
{464,68,465,549,59,230,208,655,142,997,967,110,998,952,118,287,579,301,560,150,340,810,253,947,127,681,551,473,372,258,738,739,676,208,747,562,919,760,643,199,728,639,426,453,739,655,468,666,528,940}
{900,437,525,731,184,309,270,651,423,940,687,751,815,659,628,190,678,241,399,676,631,861,483,510,562,312,883,900,914,926,542,163,284,934,910,273,403,719,87,97,802,840,374,268,31,510,972,314,114,342}
Returns: 60192
680
369
{502,408,954,550,891,566,368,233,451,969,570,982,356,800,881,166,248,349,665,908,808,441,952,503,525,612,959,514,254,447,716,307,253,609,616,141,475,315,835,963,195,164,481,1000,973,781,99,30,494,772}
{435,53,532,808,817,680,135,371,598,446,127,237,549,317,732,59,249,325,940,550,35,268,419,790,517,895,333,50,448,589,637,865,718,325,481,334,835,78,842,105,105,436,865,544,942,289,338,532,209,221}
Returns: 384880
966
179
{21,579,199,199,131,58,124,171,606,306,695,94,35,372,262,930,258,725,217,788,218,81,802,781,577,402,164,210,871,217,705,591,541,485,226,782,752,741,606,670,105,927,684,597,442,845,739,888,154,188}
{702,861,387,22,457,542,68,55,361,23,22,128,240,323,608,141,534,690,562,487,913,471,887,606,671,186,734,801,39,597,861,893,111,345,767,689,228,406,895,285,608,383,111,506,897,530,344,993,257,836}
Returns: 881784
100
100
{ 100, 32 }
{ 100, 42 }
Returns: 10000
1000
1000
{ 1000 }
{ 1000 }
Returns: 1000000
500
500
{ 1000 }
{ 1000 }
Returns: 1000000
900
900
{ 999 }
{ 999 }
Returns: 998001
4
5
{ 3 }
{ 9 }
Returns: -1
10
10
{ 12, 20, 30 }
{ 12, 20, 30 }
Returns: 144
150
10
{ 150 }
{ 10 }
Returns: 1500
51
51
{ 51 }
{ 51 }
Returns: 2601
7
3
{ 7, 8 }
{ 3, 4 }
Returns: 21
900
900
{ 1000 }
{ 1000 }
Returns: 1000000
10
10
{ 100, 10 }
{ 100, 10 }
Returns: 100
20
20
{ 30, 25 }
{ 30, 25 }
Returns: 625
10
20
{ 2 }
{ 3 }
Returns: -1
5
5
{ 5, 6 }
{ 5, 6 }
Returns: 25
500
500
{ 600, 700 }
{ 600, 700 }
Returns: 360000
20
44
{ 36, 42, 18, 37, 33, 5, 30, 10, 29, 9, 11, 16, 48, 50, 34, 44, 33, 12, 31, 41 }
{ 42, 45, 46, 24, 23, 21, 21, 8, 26, 25, 48, 12, 10, 45, 18, 6, 12, 22, 42, 45 }
Returns: 1845
3
7
{ 1000 }
{ 1000 }
Returns: 1000000
5
5
{ 5 }
{ 5 }
Returns: 25
100
100
{ 100, 32 }
{ 100, 42 }
Returns: 10000
1000
1000
{ 1000 }
{ 1000 }
Returns: 1000000
500
500
{ 1000 }
{ 1000 }
Returns: 1000000
900
900
{ 999 }
{ 999 }
Returns: 998001
4
5
{ 3 }
{ 9 }
Returns: -1
10
10
{ 12, 20, 30 }
{ 12, 20, 30 }
Returns: 144
150
10
{ 150 }
{ 10 }
Returns: 1500
51
51
{ 51 }
{ 51 }
Returns: 2601
7
3
{ 7, 8 }
{ 3, 4 }
Returns: 21
900
900
{ 1000 }
{ 1000 }
Returns: 1000000
10
10
{ 100, 10 }
{ 100, 10 }
Returns: 100
20
20
{ 30, 25 }
{ 30, 25 }
Returns: 625
10
20
{ 2 }
{ 3 }
Returns: -1
5
5
{ 5, 6 }
{ 5, 6 }
Returns: 25
500
500
{ 600, 700 }
{ 600, 700 }
Returns: 360000
20
44
{ 36, 42, 18, 37, 33, 5, 30, 10, 29, 9, 11, 16, 48, 50, 34, 44, 33, 12, 31, 41 }
{ 42, 45, 46, 24, 23, 21, 21, 8, 26, 25, 48, 12, 10, 45, 18, 6, 12, 22, 42, 45 }
Returns: 1845
3
7
{ 1000 }
{ 1000 }
Returns: 1000000
5
5
{ 5 }
{ 5 }
Returns: 25
1000
1000
{1000 }
{1000 }
Returns: 1000000
5
7
{5 }
{8 }
Returns: 40
3
7
{7 }
{3 }
Returns: 21
2
2
{2, 3 }
{2, 3 }
Returns: 4
3
3
{2 }
{2 }
Returns: -1
7
3
{6 }
{9 }
Returns: 54
1000
1000
{888 }
{1000 }
Returns: -1
17
5
{19, 10, 12, 40 }
{12, 20, 15, 5 }
Returns: 200
5
8
{6, 9, 3 }
{7, 4, 5 }
Returns: -1
1
1
{2, 2 }
{2, 4 }
Returns: 4
5
4
{2, 3, 3, 3, 3 }
{2, 7, 7, 4, 2 }
Returns: -1
7
3
{3 }
{7 }
Returns: 21
7
5
{3 }
{3 }
Returns: -1
3
3
{3, 4 }
{3, 4 }
Returns: 9
5
5
{5, 6 }
{5, 6 }
Returns: 25
1
1
{1, 2 }
{1, 2 }
Returns: 1
5
6
{999 }
{999 }
Returns: 998001
3
4
{3 }
{5 }
Returns: 15
3
3
{10, 1 }
{10, 1 }
Returns: 100
6
9
{3, 18 }
{18, 10 }
Returns: 180
5
5
{1000, 5, 1000 }
{1000, 5, 1000 }
Returns: 25
1
1
{1000 }
{1000 }
Returns: 1000000
3
3
{4, 5 }
{4, 5 }
Returns: 16