C++ O(nlogn) solution


  • 0
    I

    struct MyComp :
    public binary_function<int,int,bool> {
    public:
    bool operator() (int p,int q) {
    return p<q;
    }
    };

    class Solution {
    public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
    if(envelopes.empty()) return 0;
    sort(envelopes.begin(),envelopes.end(),[](pair<int,int> & p,pair<int,int> &q) {
    if(p.first==q.first)
    return q.second<p.second;
    return p.first<q.first;
    });
    vector<int> res;
    res.reserve(envelopes.size());
    for(auto e:envelopes) {
    auto it=lower_bound(res.begin(),res.end(),e.second,MyComp());
    if(it==res.end()) res.push_back(e.second);
    else *it=e.second;
    }
    return res.size();
    }
    };


Log in to reply
 

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