There is a problem from the university that was given to me to figure out the solution, language doesn't matter, even pseudo code is fine
P.S Maybe the solution is on the surface, don't beat me plz
Input: The first line of the input contains two integers N - the number of rectangles K - the number of rectangles we need to cover
Each of the next N lines contains four integers x1; y1; x2; y2; - coordinates of the bottom-left and top-right corners of the rectangles.
Output:
Minimum length of the square such that at least K rectangles fit there.
(Please help me, I have no idea at all)
CodePudding user response：
It seems you don't need to arrange the rectangles, just cover them. So the algorithm is indeed pretty simple:
- find xMin, xMax, yMin, yMax
- return max(xMax - xMin, yMax - yMin)
By finding the mins and maxes you see the area covered in both directions and because you need to cover with a square not a rectangle one side of the square needs to be as big as the larger side of the rectangle to be able to cover everything.
Btw. the rectangle (xMin, yMin, xMax, yMax) is the so called bounding box.