Friday, December 24, 2010

Nesting envelopes

Given k different types of envelopes. The dimensions of envelope type i are xi × yi. You can place envelope A inside envelope B if and only if the dimensions A are
strictly smaller than the dimensions of B. how many possible combination you can have?

1 comment:

  1. Build directed graph, do topological sorting then scan from the lowest and calculate: d [u] = sum d [v], where v are u's children.