leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1834.cpp (1077B)

      1 class Solution {
      2     struct item {
      3         int index, et, pt;
      4         item(int i, int e, int p) : index(i), et(e), pt(p) {}
      5         friend bool operator<(const item &i1, const item &i2) {
      6             return (i1.pt > i2.pt) || (i1.pt == i2.pt && i1.index > i2.index);
      7         }
      8     };
      9 
     10   public:
     11     vector<int> getOrder(vector<vector<int>> &tasks) {
     12         vector<item> ss;
     13         for (int i = 0; i < tasks.size(); i++)
     14             ss.push_back({i, tasks[i][0], tasks[i][1]});
     15         sort(ss.begin(), ss.end(), [](const item &i1, const item &i2) { return (i1.et < i2.et); });
     16 
     17         vector<int> res;
     18         priority_queue<item> pq;
     19         int t = 0;
     20         for (int i = 0; i < ss.size();) {
     21             if (pq.empty() && t < ss[i].et) t = ss[i].et;
     22             while (i < ss.size() && ss[i].et <= t)
     23                 pq.push(ss[i++]);
     24             item it = pq.top();
     25             pq.pop();
     26             res.push_back(it.index);
     27             t += it.pt;
     28         }
     29         while (!pq.empty())
     30             res.push_back(pq.top().index), pq.pop();
     31         return res;
     32     }
     33 };