You are given an unlimited number of each of n different types of envelopes. The dimensions of envelope type i are xi × yi. In nesting envelopes inside one another, you can place envelope A inside envelope B if and only if the dimensions A are strictly smaller than the dimensions of B.
Algorithm to determine the largest number of envelopes that can be nested inside one another.?
Solution:
1. Sort all the xi's in ascending order -> nlog(n)
2. Then find the longest increasing sequence of yi's -> nlog(n)
3. complexity will be nlog(n).
Algorithm to determine the largest number of envelopes that can be nested inside one another.?
Solution:
1. Sort all the xi's in ascending order -> nlog(n)
2. Then find the longest increasing sequence of yi's -> nlog(n)
3. complexity will be nlog(n).
No comments:
Post a Comment