Stacking boxes into fewest number of stacks efficiently?

Question

I got this question in an online coding challenge.

Given a list of boxes with length and widths (l, h), output the minimum number of stacks needed to contain all boxes, given that you can stack one box on top of another if its length and width are less than the other box's.

I can't figure out how to come up with a polynomial time solution. I've built a brute force solution that creates all possible stack arrangements recursively (start with N stacks. Then for each stack, try putting it on top of each other stack. Then recursively generate all stack possibilities given the new stack arrangement.), and then returns the smallest number of stacks needed.

I've sped it up with a few optimizations:

• If you can stack box A on top of box B and box C, and you can stack box B on top of box C, then do not consider stacking box A on box C.
• Memoize the stack arrangements, only considering the bottom and top levels of the stacks

Here's the python code for this solution:

from time import time

def all_stacks(bottom, top, d={}):

    memo_key = (tuple(bottom), tuple(top))
    if memo_key in d:
        # print "Using MEMO"
        return d[memo_key]

    res = len(bottom)
    found = False
    stack_possibilities = {}
    # try to stack the smallest boxes in all the other boxes
    for j, box1 in enumerate(bottom):
        stack_possibilities[j] = []
        for i, box2 in enumerate(top[j:]):
            # box1 fits in box2
            if fits(box2, box1):
                stack_possibilities[j].append(i + j)
                found = True

    for fr, to_list in stack_possibilities.iteritems():
        indices_to_keep = []
        for box_ind in to_list:
            keep = True
            for box_ind_2 in to_list:
                if fits(top[box_ind], top[box_ind_2]):
                    keep = False
            if keep:
                indices_to_keep.append(box_ind)
        stack_possibilities[fr] = indices_to_keep


    if found:
        lens = []
        for fr, to_list in stack_possibilities.iteritems():
            # print fr
            for to in to_list:
                b = list(bottom)
                t = list(top)
                t[to] = t[fr]
                del b[fr]
                del t[fr]
                lens.append(all_stacks(b, t, d))
        res = min(lens)

    d[memo_key] = res

    return res

def stack_boxes_recursive(boxes):
    boxes = sorted(boxes, key=lambda x: x[0] * x[1], reverse=False)
    stacks = all_stacks(boxes, boxes)
    return stacks

def fits(bigbox, smallbox):
    b1 = smallbox[0] < bigbox[0]
    b2 = smallbox[1] < bigbox[1]
    return b1 and b2


def main():

    n = int(raw_input())
    boxes = []
    for i in range(0,n):
        l, w = raw_input().split()
        boxes.append((long(l), long(w)))
    start = time()
    stacks = stack_boxes_recursive(boxes)
    print time() - start

    print stacks


if __name__ == '__main__':
    main()

Input

17
9 15
64 20
26 46
30 51
74 76
53 20
66 92
90 71
31 93
75 59
24 39
99 40
13 56
95 50
3 82
43 68
2 50

Output:

33.7288980484
6

The algorithm solves a 16 box problem in a few seconds (1-3), a 17 box problem in ~30 seconds. I'm pretty sure this is exponential time. (Since there's an exponential number of stack arrangements).

I'm pretty sure there's a polynomial time solution, but I don't know what it is. One of the issues is that memoization depends on the current stack arrangements, meaning you have to do more computations.

Answer 1

Let's build a graph, where there is vertex for each box and an edge from a box A to a box B if A can be stacked on top of B. This graph is acyclic (because "can stack on top" is a transitive relation and a boxed can't stacked on top of itself).

Now we need to find the minimum path cover of this graph. It's a standard problem and it's solved this way:

1. Let's build a bipartite graph (each vertex in the original graph gets two "copies" in the left and the right part). For each A->B edge in the original graph, there is an edge between the left copy of A and the right copy of B.

2. The answer is number of boxes minus the size of the maximum matching in the bipartite graph.

The bipartite graph as O(n) vertices and O(n^2) edges. If we use, for instance, Kuhn's algorithm to find a matching, the total time complexity is O(n^3), where n is the number of boxes.