LCS 02-完成一半题目

有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目，整型数组 questions
中每个数字对应了每道题目所涉及的知识点类型。 若每位扣友选择不同的一题，请返回被选的 N 道题目至少包含多少种知识点类型。 示例 1：

输入：questions = [2,1,6,2] > >输出：1 > >解释：有 2 位扣友在 4 道题目中选择 2 题。 >
可选择完成知识点类型为 2 的题目时，此时仅一种知识点类型 > 因此至少包含 1 种知识点类型。 示例 2： >输入：questions = [1,5,1,3,4,5,2,5,3,3,8,6] > >输出：2 > >解释：有 6 位扣友在 12 道题目中选择题目，需要选择 6 题。 >
选择完成知识点类型为 3、5 的题目，因此至少包含 2 种知识点类型。 提示： - questions.length == 2*n - 2 <= questions.length <= 10^5 - 1 <= questions[i] <= 1000

思路就是找零钱。先选出现频次最多，然后再选次多的，直到为每个人都选到知识点。

class Solution {
public:
    int halfQuestions(vector<int>& questions) {
        int n = questions.size(), p = n / 2;

        unordered_map<int, int> map;
        for (auto e : questions) map[e]++;

        vector<std::pair<int, int>> vec;
        for (auto e : map) vec.push_back(e);

        // 从大到小排序
        sort(vec.begin(), vec.end(), [](std::pair<int, int> p1, std::pair<int, int> p2) {
            return p1.second > p2.second;
        });

        int res = 0;
        int cnt = 0;
        for (auto e : vec) {
            res++;
            cnt += e.second;
            if (cnt >= p) return res;
        }
        return res;
    }
};