1
class Solution {
2
 public:
3
  vector<int> getOrder(vector<vector<int>> &tasks) {
4
    // we use priority queue to get the least processing time from the available
5
    // server implement a min heap
6

7
    // dp is double pair
8
    // sp is single pair
9
    using dp = pair<long int, pair<long int, long int>>;
10
    using sp = pair<long int, long int>;
11
    priority_queue<sp, vector<sp>, greater<sp>> pq;
12
    int len = tasks.size();
13
    // we can rearrage the tasks but we can't get the index in the original
14
    // array
15
    vector<dp> rearrange;
16
    for (long int i = 0; i < len; i++) {
17
      rearrange.push_back({tasks[i][0], {tasks[i][1], i}});
18
    }
19

20
    // rearrange contains the same as tasks but with extra value "index" in its
21
    // original array
22

23
    // sort in the ascending order of  their enqueue time
24
    // if two tasks have same enqueue time it will sort the one which has the
25
    // less processing time
26
    sort(rearrange.begin(), rearrange.end());
27
    long int i = 0;
28
    long int finishTime = rearrange[0].first;
29
    long int k = tasks.size();
30

31
    vector<int> res;
32
    while (k) {
33
      while (i < len && finishTime >= rearrange[i].first) {
34
        // push the processing time and the index
35
        pq.push({rearrange[i].second.first, rearrange[i].second.second});
36
        i++;
37
      }
38

39
      // pick the task which is available upto the current finishTime and with
40
      // the less processing time
41
      auto [time, ind] = pq.top();
42
      pq.pop();
43

44
      // processing the tasks take "time"
45
      finishTime += time; // the cpu is now idle at the time finishTime
46
      res.push_back(ind);
47

48
      // now i points to the next task
49
      // if there are no tasks left in pq
50
      //  and the next tasks enqueue time is larger than the current finishing
51
      //  time
52
      // we start with the task enqueue time
53
      if (pq.empty() && (i < len && finishTime < rearrange[i].first))
54
        finishTime = rearrange[i].first;
55

56
      k--;
57
    }
58
    return res;
59
  }
60
};