total-cost-to-hire-k-workers

Total cost to hire k workers

Problem link

Solutions

Solution.cpp

// https://leetcode.com/problems/total-cost-to-hire-k-workers/

class Solution {
 public:
  long long totalCost(vector<int>& costs, int k, int c) {
    int n = costs.size();
    long long ret{};
    set<tuple<int, int, int>> pq;
    unordered_set<int> seen;
    for (int i = 0; i < c; ++i) {
      pq.insert({costs[i], i, 1});
      pq.insert({costs[n - 1 - i], n - 1 - i, -1});
    }

    for (int i = 0, l = c, r = n - 1 - c; i < k; ++i) {
      auto [val, id, dir] = *pq.begin();
      pq.erase(pq.begin());

      if (!costs[id]) {
        --i;
        continue;
      }

      ret += val;
      costs[id] = 0;
      if (dir == 1) {
        if (l < n) {
          if (costs[l]) pq.insert({costs[l], l, dir});
          ++l;
        }
      } else {
        if (r >= 0) {
          if (costs[r]) pq.insert({costs[r], r, dir});
          --r;
        }
      }
    }
    return ret;
  }
};

Tags

• Priority queue