Distant Barcodes LeetCode solution in C++

1
class Solution {
2
 public:
3
  struct comp {
4
    bool operator()(pair<int, int> &a, pair<int, int> &b) {
5
      return a.first < b.first;
6
    }
7
  };
8

9
  vector<int> rearrangeBarcodes(vector<int> &barcodes) {
10
    unordered_map<int, int> hmap;
11
    int n = barcodes.size();
12
    if (n == 1) return barcodes;
13

14
    for (auto &bar : barcodes) {
15
      hmap[bar]++;
16
    }
17

18
    vector<int> ans;
19
    priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
20

21
    for (auto &it : hmap) {
22
      pq.push({it.second, it.first});
23
    }
24

25
    while (pq.size() > 1) {
26
      auto firstBar = pq.top();
27
      pq.pop();
28

29
      auto secondBar = pq.top();
30
      pq.pop();
31

32
      ans.push_back(firstBar.second);
33
      ans.push_back(secondBar.second);
34

35
      --firstBar.first;
36
      --secondBar.first;
37

38
      if (firstBar.first > 0) {
39
        pq.push(firstBar);
40
      }
41

42
      if (secondBar.first > 0) {
43
        pq.push(secondBar);
44
      }
45
    }
46

47
    if (pq.size()) {
48
      ans.push_back(pq.top().second);
49
      pq.pop();
50
    }
51

52
    return ans;
53
  }
54
};