Wednesday, June 15, 2016

Align Rectangle

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. 

我们先做一个简单的答案。假设题目并不要求所用的行数最小。这样就不用排序每行的矩形。

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
  List<List<Box>> alignBox(List<Box> boxes, int width) {
    List<List<Box>> result = new ArrayList<>();
    
    if (boxes == null || boxes.size() == 0 || width <= 0) {
      return result;
    }
    
    // step 1: group all the same-height boxes together
    Map<Integer, List<Box>> map = new HashMap<>();
    for (Box box : boxes) {
      if (map.containsKey(box.height)) {
        List<Box> list = map.get(box.height);
        list.add(box);
        map.put(box.height, list);
      } else {
        List<Box> list = new ArrayList<>();
        list.add(box);
        map.put(box.height, list);
      }
    }
    
    
    // step 2: align the box, put the boxes with the same height in the same row, if it cannot fit
    // one row, put into another
    for (Integer height : map.keySet()) {
      List<Box> rowBoxes = map.get(height);
      List<Box> alignedBoxes = new ArrayList<>();
      int currWidth = 0;
      for (Box box : rowBoxes) {
        if (currWidth + box.width <= width) {
          alignedBoxes.add(box);
          currWidth += box.width;
        } else {
          // First add the previous row into the reuslt and clear the row
          result.add(new ArrayList<>(alignedBoxes));
          alignedBoxes.clear();
          currWidth = 0;
          
          // Then add the box to next row
          alignedBoxes.add(box);
          currWidth += box.width;
          
          
        }
      }
      
      // put the current row into the result, for the case the total width of the
      // current row is less than the given width
      result.add(alignedBoxes);
    }
    
    return result;
  }
  
  public static void main(String[] args) {
    Solution sol = new Solution();
    List<Box> boxes = new ArrayList<>();
    
    boxes.add(new Box(2, 1));
    boxes.add(new Box(2, 5));
    boxes.add(new Box(1, 4));
    boxes.add(new Box(1, 3));
    boxes.add(new Box(4, 2));
    boxes.add(new Box(2, 3));
    boxes.add(new Box(5, 2));
    boxes.add(new Box(1, 3));
    boxes.add(new Box(5, 2));
    
    List<List<Box>> result = sol.alignBox(boxes, 5); 
    
    for (List<Box> row : result) {
      for (Box box : row) {
        System.out.print(box.height + ", " + box.width + ", ");
      }
      
      System.out.println("");
    }
  }
}

class Box {
  public int height;
  public int width;
  
  public Box(int height, int width) {
    this.width = width;
    this.height = height;
  }
}

The output:
1, 4, 
1, 3, 
1, 3, 
2, 1, 
2, 5, 
2, 3, 
4, 2, 

5, 2, 5, 2, 

我们从结果可以看见第一列是height, 第二列是width。如果限定的每行最长的宽度是5. 当height = 2的时候,我们用了3行来align 这 3个box. 实际上我们可以把2, 1 以及 2, 3 merge 到一行,这样其实用2行就可以align 高度为2 的矩形了。

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
  List<List<Box>> alignBox(List<Box> boxes, int width) {
    List<List<Box>> result = new ArrayList<>();
    
    if (boxes == null || boxes.size() == 0 || width <= 0) {
      return result;
    }
    
    // step 1: group all the same-height boxes together
    Map<Integer, List<Box>> map = new HashMap<>();
    for (Box box : boxes) {
      if (map.containsKey(box.height)) {
        List<Box> list = map.get(box.height);
        list.add(box);
        map.put(box.height, list);
      } else {
        List<Box> list = new ArrayList<>();
        list.add(box);
        map.put(box.height, list);
      }
    }
    
    
    // step 2: align the box, put the boxes with the same height in the same row, if it cannot fit
    // one row, put into another
    for (Integer height : map.keySet()) {
      List<Box> rowBoxes = map.get(height);
      // Sort the box according to the width
      Collections.sort(rowBoxes, new MyBoxComparator());
      
      List<Box> alignedBoxes = new ArrayList<>();
      int widthLeft = width;
      while (!rowBoxes.isEmpty()) {
        if (widthLeft > 0) {
          int nextBoxIndex = findNextBox(rowBoxes, widthLeft);
          if (nextBoxIndex != -1) {
            Box nextBox = rowBoxes.get(nextBoxIndex);
            alignedBoxes.add(nextBox);
            rowBoxes.remove(nextBoxIndex);
            widthLeft -= nextBox.width;
          } else {
            widthLeft = 0;
          }
        } else {
          result.add(new ArrayList<>(alignedBoxes));
          alignedBoxes.clear();
          widthLeft = width;
        }
      }
      
      // put the current row into the result, for the case the total width of the
      // current row is less than the given width
      result.add(alignedBoxes);
    }
    
    return result;
  }
  
  class MyBoxComparator implements Comparator<Box> {
    @Override
    public int compare(Box a, Box b) {
      return a.width - b.width;
    }
  }
  
  // Find the box with width equal to the target, 
  // if does not exist, return the one just smaller than the target
  int findNextBox(List<Box> boxes, int width) {
    int lo = 0;
    int hi = boxes.size() - 1;
    
    while (lo + 1 < hi) {
      int mid = lo + (hi - lo) / 2;
      if (boxes.get(mid).width == width) {
        return mid;
      } else if (boxes.get(mid).width > width) {
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    
    if (boxes.get(hi).width <= width) {
      return hi;
    } else if (boxes.get(lo).width <= width){
      return lo;
    } else {
      return -1;
    }
  }
  
  public static void main(String[] args) {
    Solution sol = new Solution();
    List<Box> boxes = new ArrayList<>();
    
    boxes.add(new Box(2, 1));
    boxes.add(new Box(2, 5));
    boxes.add(new Box(1, 4));
    boxes.add(new Box(1, 3));
    boxes.add(new Box(4, 2));
    boxes.add(new Box(2, 3));
    boxes.add(new Box(5, 2));
    boxes.add(new Box(1, 3));
    boxes.add(new Box(5, 2));
    
    List<List<Box>> result = sol.alignBox(boxes, 5); 
    
    for (List<Box> row : result) {
      for (Box box : row) {
        System.out.print(box.height + ", " + box.width + ", ");
      }
      
      System.out.println("");
    }
  }
}

class Box {
  public int height;
  public int width;
  
  public Box(int height, int width) {
    this.width = width;
    this.height = height;
  }
}

Output:
1, 4, 
1, 3, 
1, 3, 
2, 5, 
2, 3, 2, 1, 
4, 2, 

5, 2, 5, 2, 

No comments:

Post a Comment