solution.cpp

#include <bits/stdc++.h>
using namespace std;

bool sortV(vector<int> &a, vector<int> &b)
{
    if (a[0] == b[0])
        return a[1] > b[1];
    else
        return a[0] < b[0];
}
class Solution
{
public:
    int maxEnvelopes(vector<vector<int>> &envelopes)
    {
        if (envelopes.empty())
            return 0;
        sort(envelopes.begin(), envelopes.end(), sortV);
        int n = envelopes.size();
        vector<int> dp(n, 1);
        int ans = 1;
        for (int i = 1; i < envelopes.size(); i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (envelopes[i][1] > envelopes[j][1])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};