leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1834.cpp (1077B)

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