[Greedy] leetcode 870 Advantage Shuffle

problem: https://leetcode.com/problems/advantage-shuffle/

        In ordered to maximize the advantage of array A with respect to B, we had better choose the smallest element in array A that is larger than the element in B. After each selection, we erase the data we choose in A to avoid repetition.

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<int> res;
        multiset<int> datas(A.begin(), A.end());
        for(int i = 0;i < B.size(); i++)
        {
            // find the smallest number in array A that is larger than the element in array B
            auto it = datas.upper_bound(B[i]);
            
            if(it != datas.end())
            {
                res.push_back(*it);
                datas.erase(it);
            }
            else
            {
                res.push_back(*datas.begin());
                datas.erase(datas.begin());
            }
        }
        
        return res;
    }
};

 

上一篇:Shell脚本(十一):名企面试题 之 Shell脚本编写


下一篇:leetcode297. 二叉树的序列化与反序列化