假设我在二维坐标系（浮点坐标）的有限区域内有n个大小相等、旋转相等的方形框。方框不应重叠。现在我想再找一个空位放一个盒子。我需要一些算法技巧来解决这个问题。有什么想法吗？
应该有一个扫描线算法。你说这些方框是均匀旋转的，所以如果必要的话，你应该能够旋转坐标系，这样方框的边就平行于x和y坐标。然后我会按照y坐标的顺序对方框进行排序。
现在试着把一个盒子放在尽可能低的位置。从排序的框中读取，找到所有低到足以干扰放置的框，并创建这些框的有序集合（例如，红黑树或类似的容器类）。现在沿着这组盒子扫描，看看是否有足够大的间隙来放置盒子。如果没有，请使用原始排序的框列表来查找并删除最低的框，这样您就可以考虑将新框放在最低框的正上方，这样它就不会干扰这一点。从排序的列表中添加更多的框，以覆盖所有高到足以干扰此新的可能高度的框。跟踪你从列表中删除方框的位置，并检查那里是否有足够大的缺口来容纳一个方框。如果没有，请重复此练习，直到在可能的区域顶部找到间隙或空间不足。
这看起来像是初始排序的成本为N log N，然后每个框插入和删除排序集中的框的成本最多为log N。检查间隙并不比这更昂贵，因为你只在刚取下盒子的地方检查间隙。所以我认为总成本是N log N。