1
class Solution {
2
 public:
3
  int minSetSize(vector<int> &arr) {
4
    const int n = 1e5 + 10;
5
    int a[n] = {0};
6
    for (int i = 0; i < arr.size(); i++) {
7
      a[arr[i]]++;
8
    }
9
    priority_queue<int> maxh;
10
    for (int i = 0; i < n; i++) {
11
      maxh.push(a[i]);
12
    }
13
    int sum = 0;
14
    int count = 0;
15

16
    while (sum < (arr.size() / 2)) {
17
      sum = sum + maxh.top();
18
      maxh.pop();
19
      count++;
20
    }
21
    return count;
22
  }
23
};