s*****n
发帖数: 162 | 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! | g****y
发帖数: 240 | 2 看不懂题目，x,y 和rectangle的关系是什么？ | m*4
发帖数: 1341 | 3 你说这几道题都是你自己转述的嘛？感觉要求都讲得不清不楚的。
and
【在 s*****n 的大作中提到】
: 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
| R******1
发帖数: 58 | 4 Are there any other requirements? Like, the allocation should be optimal in
the sense that one can squeeze in as many rectangles as possible...
It reminds me of the first Dropbox puzzle. | s*****n
发帖数: 162 | 5 呵呵，不好意思，确实说的有些不清楚。如果有什么不明白的，我负责解释：）
这题先不考虑是否最优分配，能分配就行。
这题可以这么理解，有一块矩形内存，每次从里面分配一个小块的空闲内存（也是矩形
）。问如何组织剩余的空间。 | s*****n
发帖数: 162 | 6 这里x和y表示需要分配的新的矩形的长和宽。
【在 g****y 的大作中提到】
: 看不懂题目，x,y 和rectangle的关系是什么？
| l***i
发帖数: 1309 | 7 there needs to be some goals you want to achieve, e.g. you want allocation
to be fast, that is, in O(n) time or O(n^2) time you want to find a valid
rectangle for allocation.
Another goal is to be space efficient, that is, you want to pack in as many
rectangle as possible, given a sequence of requests.
Achieving either one is hard. | f*****7
发帖数: 92 | 8 大牛，这题怎么看着像malloc free，把矩形的每一条看成是一段内存，内存就是byte
array嘛，关键是怎么写malloc/free？跟着G卧佛点进来，再恭喜下~~ |
|
