Russian Doll Envelopes

https://leetcode.com/problems/russian-doll-envelopes/description/

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 is3([2,3] => [5,4] => [6,7]).

Thoughts

给定一堆pair，要求找出满足pair-wise递增最长序列。一维的知道怎么做，现在要用一维的思想解决二维的。直接套用一维LIS把元素做pair-wise比较是很麻烦的，比如[(1, 1), (2,3),(3,2),(3,4)] ，对长度为2的LIS要同时保留(2, 3)和(3, 2)才能保证后面的结果正确。 换个思路，先对它们其中一个值(比如宽)进行排序, 那么每个元素都比前一个元素的宽大了。 如果排序遇到宽相等情况, 把高更大的排在前面, 能避免在下一步里把等宽的放进序列里。接着针对剩下的元素, 直接用一维LIS解决，这样能保证找出来的LIS满足高和宽都是递增的。

针对一维LIS问题，除了O(N^2)的DP解法，还有O(NlgN)的二分法。

Code

/*
 * @lc app=leetcode id=354 lang=cpp
 *
 * [354] Russian Doll Envelopes
 */
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
        vector<int> tails;
        for (const auto &e : envelopes) {
            auto iter = lower_bound(tails.begin(), tails.end(), e[1]);
            if (iter == tails.end()) {
                tails.push_back(e[1]);
            } else {
                *iter = e[1];
            }
        }
        return tails.size();
    }
};

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int n = envelopes.length, end = 0;
        if (n == 0) {
            return 0;
        }
        int[] tails = new int[n];
        for (int i = 0; i < n; i++) {
            int pos = lowerBound(tails, envelopes[i][1], end);
            tails[pos] = envelopes[i][1];
            if (pos == end) {
                end++;
            }
        }

        return end;
    }

    private int lowerBound(int[] tails, int target, int end) {
        int start = 0;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (tails[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

Analysis

时间复杂度O(NlgN). 空间O(N).