Advertisement
urmisaha

Shortest Job First

Oct 24th, 2019
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define tii tuple<int, int, int>
  3. #define mt make_tuple
  4.  
  5. int n, id, at, bt, min_i, currt; // n: no of processes
  6.  
  7. using namespace std;
  8.  
  9. void shortestjobfirst(vector<tii> processes){
  10.     priority_queue<tii, vector<tii>, greater<tii> > wait_pq;
  11.     currt = get<1>(processes[0]);
  12.     get<1>(processes[0]) = -1;
  13.     wait_pq.push(processes[0]);
  14.     while(!wait_pq.empty()){
  15.         currt += get<0>(wait_pq.top());
  16.         cout<<"id: "<<get<2>(wait_pq.top())<<endl;
  17.         wait_pq.pop();
  18.         for(int i=0; i<processes.size(); ++i)
  19.             if(get<1>(processes[i]) <= currt && get<1>(processes[i]) != -1){
  20.                 wait_pq.push(processes[i]);
  21.                 get<1>(processes[i]) = -1;
  22.             }
  23.     }
  24. }
  25.  
  26. int main(){
  27.     ios_base::sync_with_stdio(false);
  28.     cin>>n;
  29.     vector<tii> processes(n);
  30.     for(int i=0; i<n; ++i){
  31.         cin>>id>>at>>bt;
  32.         processes[i] = mt(bt, at, id);
  33.     }
  34.     // sort with arrival time
  35.     for(int i=0; i<n; ++i){
  36.         min_i = i;
  37.         for(int j=i+1; j<n; ++j){
  38.             if(get<1>(processes[j]) < get<1>(processes[i]))
  39.                 min_i = j;
  40.         }
  41.         if(min_i == i)
  42.             continue;
  43.         tii t = processes[i];
  44.         processes[i] = processes[min_i];
  45.         processes[min_i] = t;
  46.     }
  47.     shortestjobfirst(processes);
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement