Question:给你a list of rectangle 让你把它们放在一个坐标平面上并align，从左往右放矩形，最右边有一个边界，不能超界，每个矩形提供getLength(), getWidth()，要保证每一行矩形的中心都在一条直线上，一行放不满另起一行，但是不能有overlap.
Solution:
基本的idea是首先遍历所有的rectangle, 建立一个HashMap<Integer, List<Rectangle>>, 把所有相同height的rectangle 都 group 到一起。所以这个map, key 存的是 height, value是具有相同height的rectangle。这样做的目的是相同height的rectangle需要排列在一行，因为题目要求每一行矩形的中心都在一条直线上。
然后遍历这个map, 并且开始排列矩形。因为每一行的宽度有限，相同高度的矩形可能放不到一行里面。这里的规则是尽量用最少的行数放下这些矩形。我们这里可以采取一个贪心的算法。首先对于一个高度的所有rectangle, 可以先按照宽度从小到大排序。然后我们维护每一行剩下的宽度，然后从这个list里面选择比这个剩余宽度小的最宽的矩形。这种贪心的策略不一定总能找到最小的行数存下所有的矩形，但应该大部分时候都能work.
Read full article from Buttercola: Align Rectangle
No comments:
Post a Comment