Russian Doll Envelopes

题目来源
给一堆(width, height)的信封，大信封装小信封，问最多可以嵌套几个信封。实际上就是一个最长上升子序列问题，不过改成了二维的。
我是先把width排序，然后求height的最长上升子序列，写的有点乱糟糟的，不过至少AC了，代码如下：

class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end());
    vector<vector<int>> widths;
    int nums = envelopes.size();
    if (nums == 0)
        return 0;
    for (int i=0; i<nums; i++) {
        vector<int> width;
        width.push_back(envelopes[i].second);
        while (i+1 < nums && envelopes[i].first == envelopes[i+1].first) {
            width.push_back(envelopes[i+1].second);
            i++;
        }
        widths.push_back(width);
    }
    int widthNums = widths.size();
    vector<vector<int>> dp;
    vector<int> minWidth(widths[0].size(), 1);
    dp.push_back(minWidth);
    for (int i=1; i<widthNums; i++) {
        vector<int> maxEnveSoFar(widths[i].size(), 0);
        for (int j=0; j<widths[i].size(); j++) {
            int curHeight = widths[i][j];
            int curMax = 1;
            for (int k=0; k<i; k++) {
                int l = 0, r = widths[k].size() - 1, mid = 0;
                while (l <= r) {
                    mid = (l + r) / 2;
                    if (widths[k][mid] >= curHeight)
                        r = mid - 1;
                    else
                        l = mid + 1;
                }
                if (widths[k][0] >= curHeight)
                    continue;
                else {
                    if (widths[k][mid] < curHeight)
                        curMax = max(curMax, dp[k][mid] + 1);
                    else
                        curMax = max(curMax, dp[k][mid-1] + 1);
                }
            }
            maxEnveSoFar[j] = curMax;
        }
        dp.push_back(maxEnveSoFar);
    }
    int res = 0;
    for (auto item : dp) {
        for (auto j : item)
            res = max(res, j);
    }
    return res;
}
};

看了下答案，然后再次感觉自己弱爆了，实际上只要按width升序，height降序，然后求height的最长上升子序列就可以了。
代码如下：

class Solution {
public:
    static bool cmp_first(const pair<int, int>& i, const pair<int, int>& j)
    {
        if (i.first == j.first)
            return i.second > j.second;
        return i.first < j.first;
    }

    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), cmp_first);
        int nums = envelopes.size();
        vector<int> tails(nums, 0);
        int size = 0;
        for (int i=0; i<nums; i++) {
            int l = 0, r = size;
            while (l != r) {
                int mid = (l + r) / 2;
                if (tails[mid] >= envelopes[i].second)
                    r = mid;
                else
                    l = mid + 1;
            }
            tails[l] = envelopes[i].second;
            if (l == size)
                size++;
        }
        return size;
    }
};