原题链接

模拟操作系统中进程的短作业优先调度算法

1.对于没有等待的情况，先来先服务
2.对于等待中的进程，采用运行时间短的优先
3.对于运行时间的进程，采用下标短的优先

对于进程服务，采用堆优化，时间复杂度 O（nlogn）

//定义堆的排序方法
struct cmp{
   bool operator()(vector<int>&x,vector<int>&y)
  {
     if(x[1]!=y[1])
        return x[1]>y[1];
     else
        return x[2]>y[2];
  }
};
/////////////////
priority_queue<vector<int>,vector<vector<int>>,cmp>q;

代码实现

class Solution {
public:
typedef long long ll;
    vector<int> getOrder(vector<vector<int>>& tasks) {
    int n=tasks.size();
    vector<vector<int> >mytasks;
    for(int i=0;i<n;i++)
    {
        vector<int>t=tasks[i];
        t.push_back(i);
        mytasks.push_back(t);
    } 
    sort(mytasks.begin(),mytasks.end());

    struct cmp{
        bool operator()(vector<int>&x,vector<int>&y)
        {
            //len越小越优先
            if(x[1]!=y[1])
                return x[1]>y[1];
            //下标越小越优先
            else
                return x[2]>y[2];
        }
    };

    priority_queue<vector<int>,vector<vector<int>>,cmp>q;
    vector<int>ans;
    q.push(mytasks[0]);
    ll start=mytasks[0][0];
    ll cur=1;
    while(!q.empty())
    {
        auto top=q.top();
        q.pop();
        ans.push_back(top[2]);
        start=start+top[1];
        //存在等待进程
        while(cur<n&&mytasks[cur][0]<=start)
        {
            q.push(mytasks[cur++]);
        }
        //无等待进程
        if(q.empty()&&cur<n)
            q.push(mytasks[cur++]);
    }
        return ans;
    }
};