问道G题(2)# JobHunting - 待字闺中
s*n
1 楼
Given a m * n matrix. Initially, all cells are not occupied. Write a
function allocate(x, y) (here x and y are width and height) which returns
the left-top coordinates of a
rectangle inside the matrix and marks the rectangle as occupied. All cells
of the rectangle should not be occupied when it is allocated. You do not
have to worry about the operation free().
My idea is to use a free list to record "available rectangles". When it
needs to allocate a rectangle with size (x, y), it goes through the list and
find one rectangle R whose x' >= x and y' > y. Cut and return a sub-
rectangle from R. For the rest of R, divide it into two smaller rectangles
R1 and R2 with size (x' - x, y) and (x', y' - y). Note that R1 and R2 are
overlapping. Because if it is cut into two non-overlapping sub-rectangles,
it may not satisfy future requirements when it actually can.
However, it turns out that this solution may lead to many cases which are
not easy for coding.Just imagine the cases how two rectangles may overlap.
Any suggestions are welcome!
function allocate(x, y) (here x and y are width and height) which returns
the left-top coordinates of a
rectangle inside the matrix and marks the rectangle as occupied. All cells
of the rectangle should not be occupied when it is allocated. You do not
have to worry about the operation free().
My idea is to use a free list to record "available rectangles". When it
needs to allocate a rectangle with size (x, y), it goes through the list and
find one rectangle R whose x' >= x and y' > y. Cut and return a sub-
rectangle from R. For the rest of R, divide it into two smaller rectangles
R1 and R2 with size (x' - x, y) and (x', y' - y). Note that R1 and R2 are
overlapping. Because if it is cut into two non-overlapping sub-rectangles,
it may not satisfy future requirements when it actually can.
However, it turns out that this solution may lead to many cases which are
not easy for coding.Just imagine the cases how two rectangles may overlap.
Any suggestions are welcome!
