354. Russian Doll Envelopes #

Problem #

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

Note: Rotation is not allowed.

Example:

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Problem Summary #

Given some envelopes marked with widths and heights, where the width and height are given as integer pairs (w, h). When another envelope’s width and height are both larger than this envelope’s, this envelope can be put into the other envelope, like a Russian doll.

Please calculate the maximum number of envelopes that can form a set of “Russian doll” envelopes (that is, one envelope can be placed inside another).

Note:

• Rotation of envelopes is not allowed.

Solution Ideas #

• Given a set of envelopes with widths and heights, if they form Russian dolls, ask for the maximum number of layers that can be nested. Only when one envelope’s width and height are both larger than another envelope’s can it be nested on top of the smaller envelope.
• The essence of this problem is an enhanced version of problem 300, Longest Increasing Subsequence. The condition for forming Russian dolls is being able to find a longest increasing subsequence. However, the condition in this problem is two-dimensional, requiring a longest increasing subsequence that satisfies the conditions in both dimensions. First reduce the dimension by sorting the widths. Then find the longest increasing subsequence on the heights. The method used here is the same as in problem 300. See problem 300 for a detailed explanation of the solution idea.
• This problem is a two-dimensional LIS problem. The one-dimensional LIS problem is problem 300. The three-dimensional LIS problem is problem 1691.

Code #

package leetcode

import (
	"sort"
)

type sortEnvelopes [][]int

func (s sortEnvelopes) Len() int {
	return len(s)
}
func (s sortEnvelopes) Less(i, j int) bool {
	if s[i][0] == s[j][0] {
		return s[i][1] > s[j][1]
	}
	return s[i][0] < s[j][0]
}
func (s sortEnvelopes) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func maxEnvelopes(envelopes [][]int) int {
	sort.Sort(sortEnvelopes(envelopes))
	dp := []int{}
	for _, e := range envelopes {
		low, high := 0, len(dp)
		for low < high {
			mid := low + (high-low)>>1
			if dp[mid] >= e[1] {
				high = mid
			} else {
				low = mid + 1
			}
		}
		if low == len(dp) {
			dp = append(dp, e[1])
		} else {
			dp[low] = e[1]
		}
	}
	return len(dp)
}