Customized compare

struct comp {
    bool operator() (const std::string& a, const std::string& b) const{
        if(a.size() == b.size()) {
            return a<b;
        }
        return a.size() > b.size();
    }
};
set<string, comp> st;

///////
sort(people.begin(), people.end(),
    [&](pair<int, int> a, pair<int, int> b){
        if(a.first!=b.first)return a.first>b.first;
        else return a.second<b.second;
});
or,
auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2) {
return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
};
sort(people.begin(), people.end(), comp);

646. Maximum Length of Pair Chain

https://leetcode.com/problems/maximum-length-of-pair-chain/description/
Solution 1.
    int findLongestChain(vector<vector<int>>& pairs) {
        if(pairs.size() == 0) return 0;
        sort(pairs.begin(), pairs.end(), [&](vector<int>&a, vector<int>&b){
            if(a[1]==b[1]) return a[0] < b[0];
            return a[1] < b[1];
        });
        int res = 1;
        int preVal = pairs[0][1];
        for(int i=1; i<pairs.size(); i++) {
            if(pairs[i][1] > preVal && pairs[i][0] > preVal) {
                res++;
                preVal = pairs[i][1];
            }
        }
        return res;
    }
Solution 2. Recursion
    int help(vector<vector<int>>& pairs, int preVal, int cur, int len) {
        if(cur == pairs.size()) {
            return len;
        }
        int i=cur;
        while(i<pairs.size() && pairs[i][1] == pairs[cur][1]) i++;
        i--;
        if(cur == 0)
            return help(pairs, pairs[i][1], i+1, 1);
        else if(pairs[i][0] > preVal)
            return help(pairs, pairs[i][1], i+1, len+1);
        else
            return help(pairs, preVal, i+1, len);
    }
    int findLongestChain(vector<vector<int>>& pairs) {
        if(pairs.size() == 0) return 0;
        sort(pairs.begin(), pairs.end(), [&](vector<int>&a, vector<int>&b){
            if(a[1]==b[1]) return a[0] < b[0];
            return a[1] < b[1];
        });
        return help(pairs, 0, 0, 0);
    }

451. Sort Characters By Frequency

https://leetcode.com/problems/sort-characters-by-frequency/description/
Solution 1, sort
    string frequencySort(string s) {
        int count['z'+1] = {0};
        for(char c : s) count[c]++;
        sort(s.begin(), s.end(), [&](char& a, char& b)
                   {return count[a]>count[b] || (count[a] == count[b] && a>b);});
        return s;
    }

Solution 2, without a sort
    string frequencySort(string s) {
        unordered_map<char,int> count;
        for(char c: s) count[c]++;
        map<int, string> f2s;
        for(auto &m : count) {
            char c = m.first;
            int n = m.second;
            f2s[n] += string(n, c);
        }
        string res;
        for(map<int,string>::reverse_iterator it=f2s.rbegin(); it!=f2s.rend(); it++)
            res += it->second;
        return res;
    }

406. Queue Reconstruction by Height

https://leetcode.com/problems/queue-reconstruction-by-height/description/
Solution 1. Sort and insert
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
        vector<pair<int, int>> res;
        sort(people.begin(), people.end(),
             [&](pair<int, int> a, pair<int, int> b){
                 if(a.first!=b.first)return a.first>b.first;
                 else return a.second<b.second;
             });
        for(int i=0; i<people.size(); i++) {
            res.insert(res.begin()+people[i].second, people[i]);
        }
        return res;
    }
The sort could be:
auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2) { 

    return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second); 

};

sort(people.begin(), people.end(), comp);

1. Two Sum

https://leetcode.com/problems/two-sum/description/
Solution 1. Sort the index according to its value using lambda expression and search. (6 ms)
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> idx(nums.size(),0);
        for(int i=0; i<idx.size(); i++) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](int i, int j){return nums[i]<nums[j];});
        for(int i=0, j=idx.size()-1; i<j;) {
            int x = nums[idx[i]]+nums[idx[j]];
            if(x == target) return {idx[i], idx[j]};
            else if(x>target) j--;
            else i++;
        }
        return {};

    }
Solution 2. Use a map: target - nums[i] -> i. (12 ms)
    vector<int> twoSum(vector<int>& nums, int target) {
        if(nums.size()<2) return {};
        unordered_map<int,int> mp;
        mp[target-nums[0]] = 0;
        for(int i=1; i<nums.size(); i++){
            if(mp.count(nums[i])) return {mp[nums[i]], i};
            else mp[target-nums[i]] = i;
        }
        return {};
    }

506. Relative Ranks

https://leetcode.com/problems/relative-ranks/description/
Solution 1. Lambda expression.
    vector<string> findRelativeRanks(vector<int>& nums) {
        int N = nums.size();
        if(N==0) return vector<string> {};
        vector<int> rank2idx(N);
        vector<string> res(N);

        for(int i=0; i < N; i++) rank2idx[i] = i;
        sort(rank2idx.begin(), rank2idx.end(), [&](int i, int j){return nums[i]>nums[j];});
        for(int i=3; i < N; i++) {
            res[rank2idx[i]] = to_string(i+1);
        }
        if(N>0) res[rank2idx[0]] = "Gold Medal";
        if(N>1) res[rank2idx[1]] = "Silver Medal";
        if(N>2) res[rank2idx[2]] = "Bronze Medal";
        return res;
    }

Solution 2.  Using a map.
    vector<string> findRelativeRanks(vector<int>& nums) {
        map<int, int, greater<int>> score2idx;
        vector<string> res(nums.size());
        for(int i=0;i<nums.size();i++){
            score2idx[nums[i]] = i;
        }
        int i=1;
        for(auto &x: score2idx) {
            if(i==1) res[x.second] = "Gold Medal";
            else if(i==2) res[x.second] = "Silver Medal";
            else if(i==3) res[x.second] = "Bronze Medal";
            else res[x.second] = to_string(i);
            i++;
        }
        return res;
    }
Solution 3. Use a priority_queue
    vector<string> findRelativeRanks(vector<int>& nums) {
        priority_queue<pair<int,int>> q;
        vector<string> res(nums.size());
        for(int i=0;i<nums.size();i++){
            q.push(make_pair(nums[i],i));
        }
       
        for(int i=0; i<nums.size();i++) {
            auto x = q.top();
            if(i==0) res[x.second] = "Gold Medal";
            else if(i==1) res[x.second] = "Silver Medal";
            else if(i==2) res[x.second] = "Bronze Medal";
            else res[x.second] = to_string(i+1);
            q.pop();
        }
        return res;
    }