C++ N log N solution
\nclass Solution {\npublic:\n    // Dynamic Programming with Binary Search\n    // Time complexity : O(nlogn). Sorting and binary search both take nlogn time.\n
```\nclass Solution {\npublic:\n    // Dynamic Programming with Binary Search\n    // Time complexity : O(nlogn). Sorting and binary search both take nlogn time.\n    // Space complexity : O(n). dp array of size n is used.\n    int maxEnvelopes(vector<vector<int>>& envelopes) {\n      // For each envelope, sorted by envelope[0] first, so envelope[1] is the the longest increasing\n      // sequence(LIS) problem. When envelope[0] tie, we reverse sort by envelope[1] because bigger\n      // envelope[1] can\'t contain the previous one.\n      sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {\n        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];\n      });\n      // dp keeps some of the visited element in a sorted list, and its size is length Of LIS sofar.\n      // It always keeps the our best chance to build a LIS in the future.\n      vector<int> dp;\n      for (auto envelope: envelopes) {\n        auto it = lower_bound(dp.begin(), dp.end(), envelope[1]);\n        if (it == dp.end()){\n          // If envelope[1] is the biggest, we should add it into the end of dp.\n          dp.push_back(envelope[1]);\n        } else {\n          // If envelope[1] is not the biggest, we should keep it in dp and replace the previous\n          // envelope[1] in this position. Because even if envelope[1] can\'t build longer LIS\n          // directly, it can help build a smaller dp, and we will have the best chance to build\n          // a LIS in the future. All elements before this position will be the best(smallest) LIS\n          // sor far.\n          *it = envelope[1];\n        }\n      }\n      // dp doesn\'t keep LIS, and only keep the length Of LIS.\n      return dp.size();\n    }\n};\n```
['Dynamic Programming', 'C', 'Binary Tree']