Russian Doll Envelopes

Question

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)

Example: Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Tags

• Array
• Binary Search
• LIS

Thought

reference: https://discuss.leetcode.com/topic/48160/python-o-nlogn-o-n-solution-beats-97-with-explanation

This problem is similar to that of the LIS problem. However, there are two differences here:

1. The element in the array is a tuple instead of a number
2. The order of the elements in the array is allowed to change when searching the longest subsequence.

Thus, we need to add some feature from the LIS solution for this problem:

1. We should sort the array before searching the longest subsequence.
2. We need to figure out how to compare an element in the array based on the values in the tuple.

For sorting part, a self-defined comparison function is used:

• The tuples are compared based on the first element at first. * If the first element is the same, then compare the second element. But the result of the comparison between the second elements should be reversed.

Example: [[5, 4], [3, 2], [3, 4]] will be sorted as [[3, 4], [3, 2], [5, 4]].

After sorting, we can run the LIS algorithm for the array. At this moment, since the first element in each tuple has been sorted but the second element in each tuple is sorted in reversed order, we only need to check the second element.

Code

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        def cmphelper(x, y):
            if x[0] < y[0] or (x[0] == y[0] and x[1] > y[1]):
                return -1
            else:
                return 1

        def lengthOfLIS(nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            DP = [[0, 0] for _ in nums]
            size = 0
            for item in nums:
                s, e = 0, size
                while s != e:
                    m = (s + e) / 2
                    if DP[m][1] >= item[1]:
                        e = m
                    else:
                        s = m + 1
                DP[s] = item
                size = max(s + 1, size)
            return size

        sort_envs = sorted(envelopes, cmp=cmphelper)
        return lengthOfLIS(sort_envs)