Sort pairs by first element then find LIS in second element O(nlogn)


  • 0
    H

    The only tricky part is to make sure envelopes with same width should not be counted towards the LIS sequence, for that, we use a custom sort function that returns true iff

    A.first < B.first || (A.first == B.first && A.second > B.second)

    class Solution {
    public:
        int maxEnvelopes(vector<pair<int, int>>& envelopes) {
            if (envelopes.empty())
                return 0;
            
            sort(envelopes.begin(), envelopes.end(), cmpPair);
            
            vector<int> table;
            table.push_back(envelopes[0].second);
            // below is binary search for LIS
            for (int i = 1; i < envelopes.size(); i++){
                if (envelopes[i].second > table[table.size() - 1])
                    table.push_back(envelopes[i].second);
                else
                    table[lower_bound(table.begin(), table.end(), envelopes[i].second) - table.begin()]= envelopes[i].second;
            }
            
            return table.size();
        }
        
        static bool cmpPair(const pair <int, int> &a, const pair <int, int> &b){
            return a.first < b.first || (a.first == b.first && a.second > b.second);// a.second > b.second makes sure same width envelops won't be counted towards the LIS sequence in height :p
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.