it seems very annoying that these NP-hard questions are asked in an interview, since techinically there is no algorithm part to them, yet they are hard to solve. it literally feels they dont want to hire.
Two variants of the problem:
-
Given a rectangle with h as height, w as width, and there are some holes in this rectangle with coordinates x,y given. Design an algorithm that cuts the rectangle into pieces of smaller rectangles,each as big as possible without touching the holes.
-
Given rectangle with w and h, and a set of holes with x,y, plus a set of smaller rectangles only with width and height, determine if the bigger rectangle can be completely fullfilled with smaller rectangles provided. There can be leftovers in the smaller sets, but smaller rectangles are limited by provided amount.
they have to be dfs, so try all combinations of cuts greedily, from biggest to smallest, until it fits, shrink width and then height, or height then width does not matter. each shrink, need to binary search x then y to see if a hole is in bound. if yes, shrink;if not, do the cut, and start both horizontally and vertically. Always assumes starting position from top left corner, so if a hole is here, it will shrink to a point and get skipped, so the next starting pos will be 1.x+1, y or 2.y+1,x. If a rectangle can fit, the starting point will be 1.x+w,y
2. x,y+h.
also need to take care of the overlapping issues, so probably also need a set for that, if an overlapped is found,also need to shrink.
For the second problem, i can only think of the same way of solving this, and coding it up is also a pain.
not really sure why interviewer woule be interested in these questions...
if there is really something fancy to it, please instruct...
