单线程CPU | 刷题打卡-一一网

本文正在参与掘金团队号上线活动，点击查看大厂春招职位

一、题目描述：

二、思路分析：

今天给大家分享的是力扣第237场周赛的第三题。比赛的时候没做出来。赛后学习一下思路。
首先说一下题目，大意是给出一堆任务的入队列时间和所需完成时长，单线程CPU按照某些规则选择任务执行。没有任务的时候，空闲。队列中有多个任务的时候，选择一个执行时间最短的任务优先执行。让我们返回CPU处理任务的先后顺序。

其实这道题的思路比较简单，就是直接模拟即可。但是模拟的时候需要选择一个合适的数据结构。
因为答案求得是任务的序号，所以我们这里重新包装一下给的数据。重新定义一个TASK类，里面包含任务的id和任务的入队时间和工作时间。
然后我们把任务放到一个数组里，然后按照任务的入队时间从小到大排序。
定义一个时间戳变量,记录当前的一个时间。
定义一个pointer 遍历，记录遍历到的任务。
定义一个最小堆，按照任务的执行时间从小到大排列，执行时间一样的时候按照序号从小到大。
然后就可以进行遍历了，如果堆里没有任务了，则选择从任务数组里选择第一个任务，把时间快进到那H。
然后开始查找还有没有开始时间小于等于H的任务，有的话全扔到堆里。
然后就从堆里取一个，就是要处理的一个任务。
遍历N次即可。

三、AC 代码：

class Solution {

    /**
     * @param Integer[][] $tasks
     * @return Integer[]
     */
    function getOrder($tasks) {
        $len_n = count($tasks);
        $tasksT = [];
        for ($i = 0; $i < $len_n; $i++) {
            $tasksT[] = new Task($i, $tasks[$i]);
        }
        //应该是按照开始时间升序了
        usort($tasksT, function ($a, $b) {
            return $a->time[0] - $b->time[0];
        });
        //按照执行时间升序，id升序
        $pq = new MyMinHeap();
        $pointer = 0;
        $timestamp = 0;
        $res = [];
        for ($i = 0; $i < $len_n; $i++) {
            if ($pq->isEmpty()) {
                $timestamp = max($timestamp, $tasksT[$pointer]->time[0]);
            }
            while ($pointer < $len_n && $tasksT[$pointer]->time[0] <= $timestamp) {
                $pq->insert([$tasksT[$pointer]->id, $tasksT[$pointer]->time[1]]);
                $pointer++;
            }
            $top = $pq->extract();
            $res[] = $top[0];
            $timestamp += $top[1];
        }

        return $res;
    }
}

class Task
{
    public $id;
    public $time;
    public function __construct($id, $time)
    {
        $this->id = $id;
        $this->time = $time;
    }
}



class MyMinHeap extends SplMinHeap
{
    protected function compare($a, $b)
    {
        if ($a[1] > $b[1]) {
            return -1;
        } elseif ($a[1] == $b[1]) {
            if ($a[0] > $b[0]) {
                return -1;
            } else {
                return 1;
            }
        } else {
            return 1;
        }

    }
}
复制代码