hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Single-Threaded CPU


  • Approach:

    1. First off, insert the tasks into a vector/list whatever goes with you with 3 following information. Say this as taskList.

      • enqueueTime, processingTime, taskIndex.

      • Sort this taskList based on the three above conditions. First enqueueTime, then processingTime, then taskIndex.

    2. Initiate a min-heap taskPQ. While traversing through the taskList you first need to check whether the currentTime of processing is somehow lesser than the current task's enqueue time or the mean-heap taskPQ is empty.

    3. If it is then you should reassign the currentTime as its current task's enqueue time.

    4. Now within this currentTime, you need to enqueue the tasks that have lesser enqueue time than currentTime in taskPQ.

    5. For the next task in taskPQ, you will add the processing time with currentTime.

    6. Also, add the index to the answerList.

    7. Remove the top element from taskPQ as the processing is done for this task.

    8. Keep doing this until taskPQ has elements.

    9. Return answerList at the end.


  • Time and Space Complexity:

      • Time Complexity: O(Nlog2N)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:

vector<int> getOrder(vector<vector<int>>& tasks) {

vector<pair<int, pair<int,int>>>taskList;

int n = tasks.size();

for(int i=0; i<n; i++){

taskList.push_back(make_pair(tasks[i][0], make_pair(tasks[i][1], i)));

}

sort(taskList.begin(), taskList.end());

priority_queue< pair<int,int>, vector<pair<int,int>>, greater<> >taskPQ;


int tid = 0;

long long cTime = 0;

// taskPQ.push({taskList[0].second.first, taskList[0].second.second});

vector<int>ans;

while(tid < n || !taskPQ.empty()){

if(taskPQ.empty() && cTime < taskList[tid].first){

cTime = taskList[tid].first;

}


while(tid < n && cTime >= taskList[tid].first){

taskPQ.push({taskList[tid].second.first, taskList[tid].second.second});

tid++;

}


auto topTask = taskPQ.top();

taskPQ.pop();

cTime += topTask.first;

ans.push_back(topTask.second);

}

return ans;

}

};