• 周日. 5月 26th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

1834. 单线程 CPU sort+优先队列 过了,学习vector<vector<int>>排序

admin

11月 28, 2021

1834. 单线程 CPU

给你一个二维数组 tasks ,用于表示 n​​​​​​ 项从 0 到 n - 1 编号的任务。其中 tasks[i] = [enqueueTimei, processingTimei] 意味着第 i​​​​​​​​​​ 项任务将会于 enqueueTimei 时进入任务队列,需要 processingTimei 的时长完成执行。

现有一个单线程 CPU ,同一时间只能执行 最多一项 任务,该 CPU 将会按照下述方式运行:

  • 如果 CPU 空闲,且任务队列中没有需要执行的任务,则 CPU 保持空闲状态。
  • 如果 CPU 空闲,但任务队列中有需要执行的任务,则 CPU 将会选择 执行时间最短 的任务开始执行。如果多个任务具有同样的最短执行时间,则选择下标最小的任务开始执行。
  • 一旦某项任务开始执行,CPU 在 执行完整个任务 前都不会停止。
  • CPU 可以在完成一项任务后,立即开始执行一项新任务。

返回 CPU 处理任务的顺序。

示例 1:

输入:tasks = [[1,2],[2,4],[3,2],[4,1]]
输出:[0,2,3,1]

解释:事件按下述流程运行:
– time = 1 ,任务 0 进入任务队列,可执行任务项 = {0}
– 同样在 time = 1 ,空闲状态的 CPU 开始执行任务 0 ,可执行任务项 = {}
– time = 2 ,任务 1 进入任务队列,可执行任务项 = {1}
– time = 3 ,任务 2 进入任务队列,可执行任务项 = {1, 2}
同样在 time = 3 ,CPU 完成任务 0 并开始执行队列中用时最短的任务 2 ,可执行任务项 = {1}
– time = 4 ,任务 3 进入任务队列,可执行任务项 = {1, 3}
– time = 5 ,CPU 完成任务 2 并开始执行队列中用时最短的任务 3 ,可执行任务项 = {1}
– time = 6 ,CPU 完成任务 3 并开始执行任务 1 ,可执行任务项 = {}
– time = 10 ,CPU 完成任务 1 并进入空闲状态

学习要点:

对vector<vector<int>> 排序

static bool cmp(const vector<int>& v1, const vector<int>& v2){
    if (v1[0] == v2[0]) return v1[1]>v2[1];
    return v1[0] < v2[0];
}
sort(clips.begin(), clips.end(), cmp);
for(int i=0;i<clips.size();i++){
    cout<<'['<<clips[i][0]<<','<<clips[i][1]<<']'<<',';
}
cout<<endl;

// [0,2],[1,9],[1,5],[4,6],[5,9],[8,10],

代码:

class Solution {
public:
    struct node
    {
        int s,t,id;
    };

    static bool cmp(node a, node b) 
    {
        if(a.s!=b.s) return a.s<b.s;
           else return a.t<b.t;
    }
    struct bmp{
        bool operator()(node a,node b)
        {
            if (a.t!=b.t) return a.t>b.t;
              else return a.id>b.id;
        }
    };
    vector<int> getOrder(vector<vector<int>>& tasks) {
    //sort(tasks.begin(),tasks.end(),cmp);  // 不会排序
    int n=tasks.size();
    node a[100005];
    for(int i=0;i<n;i++)
    {
        a[i].s=tasks[i][0];
        a[i].t=tasks[i][1];
        a[i].id=i;
    }
    sort(a,a+n,cmp);
    long long curtime=a[0].s;
    int k=0;
    vector<int> res;
    priority_queue<node,vector<node>,bmp> Q;
    Q.push(a[k++]);
    while(!Q.empty())
    { 
         while (a[k].s<=curtime && k<n) Q.push(a[k++]);
         node p=Q.top();
         Q.pop();
         res.push_back(p.id);
         curtime+=p.t;
         if(Q.empty() && k<n) 
         {
             Q.push(a[k]); 
             if (a[k].s>curtime) curtime=a[k].s; 
             k++;
        } 
    }
      return res;
    }
};

《1834. 单线程 CPU sort+优先队列 过了,学习vector<vector<int>>排序》有4个想法
  1. Wow, superb weblog format! How long have you been running a blog for?
    you make blogging look easy. The whole look of your website
    is wonderful, as smartly as the content material!
    You can see similar here sklep online

  2. Howdy would you mind stating which blog platform you’re using?
    I’m going to start my own blog soon but I’m having a
    tough time making a decision between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your layout seems different then most blogs and I’m looking for something completely unique.
    P.S Sorry for getting off-topic but I had to ask! I saw similar here: Najlepszy sklep

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注