3 ms·
This raises the question of exactly how to grow the rectangles, i.e. how to pick out the ones that have adjacent space to consume, what to do with the leftovers
by gruseom 17y ago
This raises the question of exactly how to grow the rectangles, i.e. how to pick out the ones that have adjacent space to consume, what to do with the leftovers after a merge (since the union of two rectangles may not be a rectangle) and so on. It's too slow to examine all the rectangles every time you want to answer one of these questions, so you need a way of arranging them. I've written code that is vaguely similar to what you suggest (but is too slow). It sorts the rectangles in one x-coordinate and then one y-coordinate, which still leaves a lot of searching to do. Perhaps keeping four sorted lists of the rectangles would help, but that's costly too, since as you coalesce rectangles you need to insert and delete from the set.