search

leetcode-pp / 91alg-7-daily-check

6 stars 0 forks source link

【Day 33 】2022-05-03 - 1834. 单线程 CPU #36

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

1834. 单线程 CPU

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/single-threaded-cpu/

前置知识

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

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

返回 CPU 处理任务的顺序。

 

示例 1：

输入：tasks = [[1,2],[2,4],[3,2],[4,1]] 输出：[0,2,3,1] 解释：事件按下述流程运行：

示例 2：

输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] 输出：[4,3,2,0,1] 解释：事件按下述流程运行：

 

提示：

tasks.length == n 1 <= n <= 105 1 <= enqueueTimei, processingTimei <= 109

ZacheryCao commented 2 years ago

Idea

Heap

Code

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        if not tasks:
            return []
        t = [[tasks[i][0], tasks[i][1], i] for i in range(len(tasks))]
        t.sort(reverse = True)
        heap = []
        ans = []
        cur = t[-1][0]
        while t:
            while t and cur>=t[-1][0]:
                start,process, index = t.pop()
                heapq.heappush(heap,[process, index])
            if t and cur < t[-1][0] and not heap:
                cur = t[-1][0]
                continue
            time, i = heapq.heappop(heap)
            ans.append(i)
            cur += time
        while heap:
            ans.append(heapq.heappop(heap)[1])
        return ans

Complexity:

Time: O(NlogN) Space: O(N)

JiangWenqi commented 2 years ago
  1. append its idx to each task;
  2. sort tasks by enqueue time in ascending sort;
  3. created a priority queue, according their process time
class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        long time = 0;
        int n = tasks.size(), idx = 0;

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

        // append the original order/index to each task to avoid getting a wrong order of result
        for (int i = 0; i < n; i++) tasks[i].push_back(i);
        // sort tasks by enqueueTime in ascending order
        sort(tasks.begin(), tasks.end());
        vector<int> res;
        // when we still have tasks left
        while (idx < n || !waitingTasks.empty()) {
            // if we don't have any waiting task, we need to update time
            if (waitingTasks.empty()) time = max(time, (long)tasks[idx][0]);
            // the task is earlier than time, it needs to line up
            while (idx < n && tasks[idx][0] <= time) {
                waitingTasks.push(make_pair(tasks[idx][1], tasks[idx][2]));
                idx++;
            }
            pair<int, int> task = waitingTasks.top();
            waitingTasks.pop();
            time += task.first;
            res.push_back(task.second);
        }

        return res;
    }
};

O(nlogn) O(n)

rzhao010 commented 2 years ago

Thoughts

we should deal with the first enqueued task first, but when a new task come, we should consider the remaining task time and the new task time

  1. if no task in the queue, continue
  2. put all tasks which early then timestamp in the queue
  3. poll the next task from queue and deal with it(timestamp addup, result record)

Code


   public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        int[][] newTasks = new int[n][3];

        for(int i = 0; i < n; i++) {
            newTasks[i][0] = tasks[i][0];
            newTasks[i][1] = tasks[i][1];
            newTasks[i][2] = i;            
        }
        Arrays.sort(newTasks, (o1, o2) -> o1[0] - o2[0]);
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((o1, o2) -> 
                                    (o1[1] != o2[1] ? o1[1] - o2[1] : o1[2] - o2[2]));

        int time = 0, resIdx = 0, enqIdx = 0;
        int[] res = new int[n];
        while (resIdx < n) {
            while (enqIdx < n && newTasks[enqIdx][0] <= time) {
                pq.offer(newTasks[enqIdx++]);
            }
            if (pq.isEmpty()) {
                time = newTasks[enqIdx][0];
                continue;
            }
            int[] nextJob = pq.poll();
            res[resIdx++] = nextJob[2];
            time += nextJob[1]; 
        }
        return res;
    }

Complexity Time: O(nlogn), O(nlogn) for quick sort, and priorityqueue poeration for O(logn) Space: O(n)

james20141606 commented 2 years ago

Day 33: 1834. Single-Threaded CPU (string, array, heap, simulation)

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        #we add task index to the tasks. Now it is start time, task index, duration
        tasks.sort()
        #sort by start time
        backlog = []
        ans = []
        time = 0
        pos = 0
        #we use pos to iterate through all the tasks
        for _ in tasks:
            if not backlog:
                #if no tasks in the backlog, fast forward to the next task's start time using pos
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                #push all the tasks starting before current time to the backlog, using heap
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1])) #only push duration and task index
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans
ghost commented 2 years ago

题目

  1. Single-Threaded CPU

思路

Simulation

代码

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        sorted_tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        sorted_tasks.sort()
        res = []
        h = []
        time = 0
        pos = 0

        for _ in sorted_tasks:
            if not h:
                time = max(time, sorted_tasks[pos][0])

            while(pos<n and sorted_tasks[pos][0]<=time):
                heapq.heappush(h,[sorted_tasks[pos][2],sorted_tasks[pos][1] ])
                pos+=1

            pt, idx = heapq.heappop(h)
            time+=pt
            res.append(idx)

        return res

复杂度

Space: O(n) Time: O(nlog(n))

ShawYuan97 commented 2 years ago

思路

将任务开始时间，索引，结束时间三元组组成一个列表，进行排序后，可以选择出最先开始执行的任务
然后使用持续时间，索引作为二元组，然后变成一个堆，就可以按照执行时间长短进行排序

关键点

代码

Python3 Code:


class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        """
        根据两条标准，1. CPU选择队列中执行时间最短的任务开始执行 2. 一旦某项任务开始执行，CPU在执行完整个任务前不会停止
        """
        # 使用堆+模拟
        tasks = [(task[0],i,task[1]) for i,task in enumerate(tasks)]
        tasks.sort()

        time = 0 # 记录当前时间
        pos = 0 # 记录当前任务索引位置
        ans =[] # 返回结果集合
        backlog = [] # 还未执行的任务列表
        for _ in tasks:
            # 如果没有未执行的任务 更新当前时间
            if not backlog:
                time = max(time,tasks[pos][0])
            # 将那些还未执行的任务 加入最小堆
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog,(tasks[pos][2],tasks[pos][1]))
                pos += 1
            d,j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans

复杂度分析

令 n 为数组长度。

Magua-hub commented 2 years ago 

class Solution {
public:
    struct Task {
        int id;
        long start_time;
        int duration;
    };

    struct cmp_by_start_time {
        bool operator() (Task &a, Task &b) {
            return a.start_time > b.start_time;
        }
    };

    struct cmp_by_duration_id {
        bool operator() (Task &a, Task &b) {
            return a.duration != b.duration ? a.duration > b.duration : a.id > b.id;
        }
    };

    vector<int> getOrder(vector<vector<int>>& tasks) {
        priority_queue<Task, vector<Task>, cmp_by_start_time> candidate_tasks;
        priority_queue<Task, vector<Task>, cmp_by_duration_id> ready_tasks;

        for(int i = 0; i < tasks.size(); i ++) 
            candidate_tasks.push(Task{i, tasks[i][0], tasks[i][1]});

        long cur_time = 0;
        vector<int> res;
        while(res.size() < tasks.size()) {
            if(ready_tasks.empty())
                cur_time = max(cur_time, candidate_tasks.top().start_time);

            while(!candidate_tasks.empty() && candidate_tasks.top().start_time <= cur_time) {
                ready_tasks.push(candidate_tasks.top());
                candidate_tasks.pop();
            }
            Task task_to_process = ready_tasks.top(); //去除当前需要处理的task
            ready_tasks.pop();
            res.push_back(task_to_process.id);
            cur_time += task_to_process.duration; //更新时间
        }
        return res;
    }
};
oneline-wsq commented 2 years ago

代码

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks=[(task[0],i,task[1]) for i,task in enumerate(tasks)]
        tasks.sort() # 按照进入队列的时间进行排序
        backlog=[]
        time=0
        ans=[]
        pos=0
        for _ in tasks:
            if not backlog:
                time=max(time,tasks[pos][0])
            while pos<len(tasks) and tasks[pos][0]<=time:
                heapq.heappush(backlog,(tasks[pos][2],tasks[pos][1]))
                pos+=1
            d,j=heapq.heappop(backlog)
            time+=d 
            ans.append(j)
        return ans

复杂度分析

时间复杂度：O(nlogn)

空间复杂苏：O(n)

houmk1212 commented 2 years ago

思路

模拟，用两个堆来排序任务的开始时间，用另一个堆模拟等待队列。

代码

class Solution {
    public int[] getOrder(int[][] tasks) {
        PriorityQueue<int[]> waitQ = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
//                重新改写数组,o1[0]表示下标，o1[1]表示执行时间
                if (o1[1] != o2[1]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[0] - o2[0];
                }
            }
        });

        PriorityQueue<int[]> timeQ = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int time = 0;
        int idnex = 0;
        int[] res = new int[tasks.length];
        for (int i = 0; i < tasks.length; i++) {
            int[] t = new int[]{tasks[i][0], i};
            timeQ.offer(t);
        }

        while (idnex < tasks.length) {
            while (!timeQ.isEmpty() && timeQ.peek()[0] <= time) {
                int[] t = timeQ.poll();
                waitQ.offer(new int[]{t[1], tasks[t[1]][1]});
            }
            if (waitQ.isEmpty() && !timeQ.isEmpty()) {
                time = timeQ.peek()[0];
            }

            if (!waitQ.isEmpty()) {
                int[] preToDo = waitQ.poll();
                res[idnex++] = preToDo[0];
                // System.out.println("taskId: " + preToDo[0] + "  time: " + time);
                time += preToDo[1];
            }
        }
        return res;
    }
}

复杂度

currybeefer commented 2 years ago

模拟题，用堆完成就好

def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        tasks.sort()
        backlog = []
        time = 0
        ans = []
        pos = 0
        for _ in tasks:
            if not backlog:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans
HuiWang1020 commented 2 years ago

Idea

sort + priorityqueue

Code

class Solution {
    public int[] getOrder(int[][] tasks) {
        if (tasks == null || tasks.length == 0) return null;
        int n = tasks.length;
        int[][] ts = new int[n][3];
        int[] ans = new int[n];

        //ts{a,b,c} a:enqueuetime b:precesstime c:index    
        for (int i = 0; i < n; i++) {
            ts[i] = new int[]{tasks[i][0], tasks[i][1], i};
        }
        Arrays.sort(ts, (a, b) -> (a[0] - b[0]));

        //sort by process time (shortest)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]));

        int tasktime = ts[0][0];
        int idx = 0, i = 0;
        while(idx < n) {
            while (i < n && ts[i][0] <= tasktime) {
                    pq.add(ts[i++]);
            }
            //empty -> go to next task
            if (pq.isEmpty()) {
                tasktime = ts[i][0];
                continue;
            }

            //update tasktime and result
            int[] cur = pq.poll();
            ans[idx++] = cur[2];
            tasktime += cur[1];  
        }     
        return ans;  
    }
}

Complexity

time=O(nlogn) space=O(n)

okbug commented 2 years ago 
var getOrder = function (tasks) {
  const queue = new MinPriorityQueue()
  tasks = tasks.map((task, index) => ({
    index,
    start: task[0],
    time: task[1]
  }))
  tasks.sort((a, b) => b.start - a.start)
  const answer = []
  let time = 0
  while (tasks.length > 0 || !queue.isEmpty()) {
    if (queue.isEmpty() && tasks[tasks.length - 1].start > time) {
      time = tasks[tasks.length - 1].start
    }

    while (tasks.length > 0) {
      if (tasks[tasks.length -1].start <= time) {
        const task = tasks.pop()
        queue.enqueue(task, task.time * 100000 + task.index)
      } else {
        break
      }
    }

    const { element: task } = queue.dequeue()
    time += task.time
    answer.push(task.index)
  }
  return answer
}
zhiyuanpeng commented 2 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        tasks.sort()
        ans = []
        will_pro = []
        time, pro = 0, 0 
        for _ in tasks:
            if not will_pro:
                #time = task[pro][0]
                time = max(time, tasks[pro][0])
            while pro < len(tasks) and tasks[pro][0] <= time:
                heapq.heappush(will_pro, (tasks[pro][2], tasks[pro][1]))
                pro += 1
            en, i = heapq.heappop(will_pro)
            ans.append(i)
            time += en
        return ans
caterpillar-0 commented 2 years ago

思路

使用两个优先队列，分别入队时间排序，和处理时间排序

代码

class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        //时间戳
        long long timestamp=0;
        //两个优先队列,因为指定了第三个参数，因此第二个参数也需要指定，不能默认了
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> entry,ready;
        //先将entry队列进行排序，分别是入队时间，编号
        for(int i=0;i<tasks.size();i++){
            entry.push(make_pair(tasks[i][0],i));
        }
        vector<int> res;
        while(!entry.empty() || !ready.empty()){
            if(ready.empty()){
                timestamp=entry.top().first;
                while(!entry.empty() && entry.top().first==timestamp){
                    int index=entry.top().second;
                    ready.push(make_pair(tasks[index][1],index));
                    entry.pop();
                }
            }
            res.emplace_back(ready.top().second);
            timestamp+=ready.top().first;
            ready.pop();
            //时间戳此时更新，需要更新entry顺序
            while(!entry.empty() && entry.top().first<=timestamp){
                int index=entry.top().second;
                ready.push(make_pair(tasks[index][1],index));
                entry.pop();
            }
        }       
        return res;
    }
};

复杂度分析

Jessie725 commented 2 years ago

Idea

3 level sort: sort by start time, sort by time using, sort by index Track the timestamp, and put all available task (start time < current timestamp) into pq

Code

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        int[][] taskIdx = new int[n][3];
        for (int i = 0; i < n; i++) {
            taskIdx[i][0] = tasks[i][0]; // start time
            taskIdx[i][1] = tasks[i][1]; // time using
            taskIdx[i][2] = i; // index
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] == b[1] ? a[2] - b[2] : a[1] - b[1]);
        Arrays.sort(taskIdx, (a, b) -> a[0] - b[0]);

        int time = 0;
        int done = 0;
        int i = 0;

        int[] res = new int[n];
        while (done < n) {
            if (pq.isEmpty()) {
                time = Math.max(time, taskIdx[i][0]);
            }
            while (i < n && taskIdx[i][0] <= time) {
                pq.offer(taskIdx[i++]);
            }
            int[] curr = pq.poll();
            res[done++] = curr[2];
            time += curr[1];
        }     
        return res;
    }
}

Complexity

Time: O(nlogn) Space: O(n)

freedom0123 commented 2 years ago 
class Solution {
    public int[] getOrder(int[][] ts) {
        int n = ts.length;
        // 将 ts 转存成 nts，保留任务编号
        int[][] nts = new int[n][3];
        for (int i = 0; i < n; i++) nts[i] = new int[]{ts[i][0], ts[i][1], i};
        // 根据任务入队时间进行排序
        Arrays.sort(nts, (a,b)->a[0]-b[0]);
        // 根据题意，先按照「持续时间」排序，再根据「任务编号」排序
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        int[] ans = new int[n];
        for (int time = 1, j = 0, idx = 0; idx < n; ) {
            // 如果当前任务可以添加到「队列」中（满足入队时间）则进行入队
            while (j < n && nts[j][0] <= time) q.add(nts[j++]);
            if (q.isEmpty()) {
                // 如果当前「队列」没有任务，直接跳到下个任务的入队时间
                time = nts[j][0];
            } else {
                // 如果有可执行任务的话，根据优先级将任务出队（记录下标），并跳到该任务完成时间点
                int[] cur = q.poll();
                ans[idx++] = cur[2];
                time += cur[1];
            }
        }
        return ans;
    }
}
liuguang520-lab commented 2 years ago

思路

使用堆 ···cpp class Solution { public: static bool comp(pair<int,vector>& a, pair<int,vector>& b)//排序函数 { return a.second[1] == b.second[1]?a.first > b.first : a.second[1] > b.second[1]; }

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

priority_queue<pair<int,vector<int>>,vector<pair<int,vector<int>>>,decltype(&comp)> Q(comp);
int size = tasks.size();
long long time = 0;
//将进入时间最早的先入队列
vector<pair<int,vector<int>>> _tasks;//为了在入队时区别自己
for(int i = 0; i< size; i++)
{
    _tasks.push_back({i,tasks[i]});
}
sort(_tasks.begin(),_tasks.end(),[&](pair<int,vector<int>> i, pair<int,vector<int>> j) {
    return i.second[0] < j.second[0];
});
vector<int> result;
int ptr = 0;
for(int i = 0; i< tasks.size(); i++)//确保不会多次入队
{
    if(Q.empty())
    {
        time = max(time,(long long)_tasks[i].second[0]);
    }
    while(ptr< size &&_tasks[ptr].second[0] <= time)
    {
        Q.emplace(_tasks[ptr]);
        ptr++;
    }
    pair<int,vector<int>> p = Q.top();
    Q.pop();
    time += p.second[1];
    result.push_back(p.first);
}
return result;

} }; ···

复杂度分析

MoonLee001 commented 2 years ago

思路

使用数组按照 enqueueTime 从小到大记录tasks的index；使用最小堆选择处理时间最小的数组；维护一个timestamp，用于判断哪些数据入堆

代码

class minHeap{
    constructor() {
        this.data = [];
    }

    compare(i, j) {
        if (this.data[i] && this.data[j]) {
            if (this.data[i][0] == this.data[j][0]) {
                return this.data[i][1] > this.data[j][1];
            } else {
                return this.data[i][0] > this.data[j][0];
            }
        }
    }

    offer(val) {
        this.data.push(val);
        this.bubbleUp(this.size() - 1);
    }

    poll() {
        const result = this.data[0];
        const last = this.data.pop();
        if (this.size() !== 0) {
            this.data[0] = last;
            this.bubbleDown(0);
        }
        return result;
    }

    bubbleUp(i) {
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2);
            if (this.compare(parent, i)) {
                this.swap(parent, i);
                i = parent;
            } else {
                break;
            }
        }
    }

    bubbleDown(i) {
        while (true) {
            const left = 2 * i + 1;
            const right = 2 * i + 2;
            let min = i;
            if (i < this.size() && this.data[left] && this.compare(min, left)) {
                min = left;
            }

            if (i < this.size() && this.data[right] && this.compare(min, right)) {
                min = right;
            }

            if (min !== i) {
                this.swap(i, min);
                i = min;
            } else {
                break;
            }
        }
    }

    size() {
        return this.data.length;
    }

    swap(i, j) {
        const temp = this.data[i];
        this.data[i] = this.data[j];
        this.data[j] = temp;
    }
}

var getOrder = function(tasks) {
    const n = tasks.length;
    const indices = tasks.map((task, index) => ({
        index,
        start: task[0]
    })).sort((a, b) => a.start - b.start).map((val) => val.index);

    const heap = new minHeap();
    let timestamp = 0;
    let ptr = 0;
    let ans = [];
    for (let i = 0; i < n; i++) {
        if (heap.data.length == 0) {
            timestamp = Math.max(timestamp, tasks[indices[ptr]][0]);
        }

        while(ptr < n && tasks[indices[ptr]][0] <= timestamp) {
            heap.offer([tasks[indices[ptr]][1], indices[ptr]]);
            ptr++;
        }

        const [process, index] = heap.poll();
        timestamp += process;
        ans.push(index);
    }
    return ans;
};

复杂度分析

yanjyumoso commented 2 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:

        n = len(tasks)
        idx = list(range(n))

        # sort index by enqueue time
        idx.sort(key=lambda x: tasks[x][0])

        ans = []
        queue = []
        time = 0
        ptr = 0
        for i in range(n):
            if not queue:
                time = max(time, tasks[idx[ptr]][0])
            while ptr < n and tasks[idx[ptr]][0] <= time:
                heapq.heappush(queue, (tasks[idx[ptr]][1], idx[ptr]))
                ptr += 1

            p, i = heapq.heappop(queue)
            time += p
            ans.append(i)

        return ans
Ellie-Wu05 commented 2 years ago

思路： Min Heap

代码

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:

        ans = []
        # 这里我们要记住原来的index
        tasks = sorted([(t[0],t[1],i) for i, t in enumerate(tasks)] )
        i = 0
        h = []
        # 用curtime表示当前时间
        curtime = tasks[0][0]

        while len(ans) < len(tasks):
            # 只要是enque time都小于curtime的，都heappush进去
            while (i<len(tasks) and tasks[i][0] <= curtime):
                heapq.heappush(h,(tasks[i][1],tasks[i][2]))
                i += 1
            if h:
                # pop 出任务进行process，这里我们不需要关心enque time，只需要proces time
                t_diff,original_index = heapq.heappop(h)
                curtime += t_diff
                ans.append(original_index)
            # when CPU is idle, set the current time to the next push task enqueue time
            elif i<len(tasks):
                curtime = tasks[i][0]
        return ans

复杂度

时间：Onlogn 空间：On

KWDFW commented 2 years ago

Day33

1834、单线程CPU

javascript #模拟

思路

1、动态求极值，构建一个堆

2、初始化堆，第一优先级执行时间，第二优先级任务索引

3、不断添加任务到堆中

4、记录已执行的任务并增加当前时间

5、返回记录的任务序列

题解

代码

var getOrder = function(tasks) {
  // 为每个 task 添加一个索引属性并按照时长排序排序
  tasks.forEach((v, i) => v.push(i));
  tasks.sort((a, b) => b[0] - a[0]);

  // 初始化小根堆/优先队列
  const heap = new PriorityQueue(function(x, y) {
    // 第一优先级为执行时间，第二优先级为任务索引
    return this.A[x][1] !== this.A[y][1]
      ? this.A[x][1] < this.A[y][1]
      : this.A[x][2] < this.A[y][2]
  });
  const ans = [];
  // CPU 时间：初始化为首个任务的开始时间
  let time = tasks[tasks.length - 1][0];

  // 保证执行完所有任务
  while (heap.size() || tasks.length) {
    // 取出任务队列中优先级最高的任务
    if (!heap.isEmpty()) {
      const task = heap.dequeue();
      ans.push(task[2]); // 记录结果
      time += task[1];  // 任务执行完毕，递增 CPU 时间
    }

    // 添加任务到任务队列
    addTask(heap, tasks, time);

    // 边界：任务队列为空（剩余任务的入队时间跨度太大，导致上一步未能添加任务）
    if (heap.isEmpty() && tasks.length) {
      // 将 CPU 时间快进到下一个任务，并添加任务到任务队列
      time = tasks[tasks.length - 1][0];
      addTask(heap, tasks, time);
    }
  }

  return ans;
};

function addTask(heap, tasks, time) {
  // 将 tasks 中入队时间不快于当前 CPU 时间的任务入队
  while (tasks.length && tasks[tasks.length - 1][0] <= time) {
    heap.enqueue(tasks.pop());
  }
}

class Heap {
  constructor(compare) {
    this.A = [];
    this.compare = compare;
  }
  size() {
    return this.A.length;
  }
  left(i) {
    return 2 * i + 1;
  }
  right(i) {
    return 2 * i + 2;
  }
  parent(i) {
    return i > 0 ? (i - 1) >>> 1 : -1;
  }
  isEmpty() {
    return this.size() === 0;
  }
  peek() {
    return this.A[0];
  }
  heapifyDown(i) {
    let p = i;
    const l = this.left(i),
      r = this.right(i),
      size = this.size();
    if (l < size && this.compare(l, p)) p = l;
    if (r < size && this.compare(r, p)) p = r;
    if (p !== i) {
      this.exchange(i, p);
      this.heapifyDown(p);
    }
  }
  heapifyUp(i) {
    const p = this.parent(i);
    if (p >= 0 && this.compare(i, p)) {
      this.exchange(i, p);
      this.heapifyUp(p);
    }
  }
  exchange(x, y) {
    const temp = this.A[x];
    this.A[x] = this.A[y];
    this.A[y] = temp;
  }
  compare() {
    throw new Error('Must be implement!');
  }
}

class PriorityQueue extends Heap {
  constructor(compare) {
    super(compare);
  }
  enqueue(node) {
    this.A.push(node);
    this.heapifyUp(this.size() - 1);
  }
  dequeue() {
    const first = this.A[0];
    const last = this.A.pop();
    if (first !== last) {
      this.A[0] = last;
      this.heapifyDown(0);
    }
    return first;
  }
}

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(n)

carterrr commented 2 years ago

class Solution { public int[] getOrder(int[][] tasks) { int len = tasks.length; // 建堆 执行完获取数组中小于等于的入堆并重新poll执行 Queue<int[]> q = new PriorityQueue<>((a,b) -> { if(a[1] == b[1]) return a[2] - b[2]; // 否则下标小的先出队 return a[1] - b[1]; // 执行时间小的先出队 }); for (int i = 0; i < len; i++) { tasks[i] = new int[]{tasks[i][0],tasks[i][1], i}; } // 排序后保留原来的下标 Arrays.sort(tasks, Comparator.comparingInt(a -> a[0])); int[] res = new int[len]; int idx = 0, i = 0, curTime = tasks[0][0]; while(i < len && tasks[i][0] <= curTime) { q.offer(tasks[i]); i++; } while(!q.isEmpty()) { int[] poll = q.poll(); curTime += poll[1]; if(i < len && curTime < tasks[i][0] && q.isEmpty()) { // 上一个任务完成了 但是没到下一个任务开始时间 队列也是空的了 直接跳过去加进来 这里是难点 curTime = tasks[i][0]; } res[idx++] = poll[2]; while(i < len && tasks[i][0] <= curTime) { // 当前时间之前的全部加入排序 用于下一次poll q.offer(tasks[i]); i ++; } } return res; } }

physicshi commented 2 years ago

思路

看题解学到的

  1. 首先要记录任务标号
  2. 我们要做的就是每次将可以到达入队时间的任务入队（入队时间不大于上一个任务的结束时间）
  3. 判断当前队列是否有可执行的任务
    • 如果有，取出任务，并且设置任务结束时间，记录任务标号
    • 如果没有，说明步骤 2 没有可以到达入队时间的任务（下一个任务的开始时间比较晚），所以需要提前加一个判断逻辑，判断下一个任务的开始时间，设置为 time

代码

const getOrder = function (tasks) {
  const answer = [];
  // 官方自带的优先队列
  const queue = new MinPriorityQueue();
  tasks = tasks.map((task, index) => ({
    index,
    start: task[0],
    time: task[1],
  }));
  // 根据任务入队时间排序
  tasks.sort((a, b) => b.start - a.start);
  let time = 0;
  while (tasks.length > 0 || !queue.isEmpty()) {
    // 队列为空，且没有到达下一个入队任务的入队时间
    // 直接将time设置为下一个入队任务的入队时间
    if (queue.isEmpty() && tasks[tasks.length - 1].start > time) {
      time = tasks[tasks.length - 1].start;
    }

    while (tasks.length > 0) {
      // 将可以到达入队时间的任务加入队列
      if (tasks[tasks.length - 1].start <= time) {
        const task = tasks.pop();
        // 传入的第二个值表示的是指定当前元素的优先级
        queue.enqueue(task, task.time * 100000 + task.index);
      } else {
        break;
      }
    }

    // 执行任务
    const { element: task } = queue.dequeue();
    // 将time设置为该任务的结束时间
    time += task.time;
    answer.push(task.index);
  }
  return answer;
};

复杂度

xingchen77 commented 2 years ago

思路

使用堆进行题目的模拟

代码

    def getOrder(self, tasks: List[List[int]]) -> List[int]:        
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        tasks.sort()
        backlog = []
        time = 0
        ans = []
        pos = 0
        for _ in tasks:
            if not backlog:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans

复杂度

时间 O(nlogn) \ 空间 O(n)

zhulin1110 commented 2 years ago

题目地址(1834. 单线程 CPU)

https://leetcode-cn.com/problems/single-threaded-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 并进入空闲状态

示例 2：

输入：tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
输出：[4,3,2,0,1]
解释：事件按下述流程运行： 
- time = 7 ，所有任务同时进入任务队列，可执行任务项  = {0,1,2,3,4}
- 同样在 time = 7 ，空闲状态的 CPU 开始执行任务 4 ，可执行任务项 = {0,1,2,3}
- time = 9 ，CPU 完成任务 4 并开始执行任务 3 ，可执行任务项 = {0,1,2}
- time = 13 ，CPU 完成任务 3 并开始执行任务 2 ，可执行任务项 = {0,1}
- time = 18 ，CPU 完成任务 2 并开始执行任务 0 ，可执行任务项 = {1}
- time = 28 ，CPU 完成任务 0 并开始执行任务 1 ，可执行任务项 = {}
- time = 40 ，CPU 完成任务 1 并进入空闲状态

 

提示：

tasks.length == n
1 <= n <= 105
1 <= enqueueTimei, processingTimei <= 109

前置知识

代码

JavaScript Code:


/**
 * @param {number[][]} tasks
 * @return {number[]}
 */
class Heap {
  constructor(compare) {
    this.A = [];
    this.compare = compare;
  }
  size() {
    return this.A.length;
  }
  left(i) {
    return 2 * i + 1;
  }
  right(i) {
    return 2 * i + 2;
  }
  parent(i) {
    return i > 0 ? (i - 1) >>> 1 : -1;
  }
  isEmpty() {
    return this.size() === 0;
  }
  peek() {
    return this.A[0];
  }
  heapifyDown(i) {
    let p = i;
    const l = this.left(i),
      r = this.right(i),
      size = this.size();
    if (l < size && this.compare(l, p)) p = l;
    if (r < size && this.compare(r, p)) p = r;
    if (p !== i) {
      this.exchange(i, p);
      this.heapifyDown(p);
    }
  }
  heapifyUp(i) {
    const p = this.parent(i);
    if (p >= 0 && this.compare(i, p)) {
      this.exchange(i, p);
      this.heapifyUp(p);
    }
  }
  exchange(x, y) {
    const temp = this.A[x];
    this.A[x] = this.A[y];
    this.A[y] = temp;
  }
  compare() {
    throw new Error('Must be implement!');
  }
}

class PriorityQueue extends Heap {
  constructor(compare) {
    super(compare);
  }
  enqueue(node) {
    this.A.push(node);
    this.heapifyUp(this.size() - 1);
  }
  dequeue() {
    const first = this.A[0];
    const last = this.A.pop();
    if (first !== last) {
      this.A[0] = last;
      this.heapifyDown(0);
    }
    return first;
  }
}

var getOrder = function(tasks) {
   // 为每个 task 添加一个索引属性并排序
  tasks.forEach((v, i) => v.push(i));
  tasks.sort((a, b) => b[0] - a[0]);

  // 初始化小根堆/优先队列
  const heap = new PriorityQueue(function(x, y) {
    // 第一优先级为执行时间，第二优先级为任务索引
    return this.A[x][1] !== this.A[y][1]
      ? this.A[x][1] < this.A[y][1]
      : this.A[x][2] < this.A[y][2]
  });
  const ans = [];
  // CPU 时间：初始化为首个任务的开始时间
  let time = tasks[tasks.length - 1][0];

  // 保证执行完所有任务
  while (heap.size() || tasks.length) {
    // 取出任务队列中优先级最高的任务
    if (!heap.isEmpty()) {
      const task = heap.dequeue();
      ans.push(task[2]); // 记录结果
      time += task[1];  // 任务执行完毕，递增 CPU 时间
    }

    // 添加任务到任务队列
    addTask(heap, tasks, time);

    // 边界：任务队列为空（剩余任务的入队时间跨度太大，导致上一步未能添加任务）
    if (heap.isEmpty() && tasks.length) {
      // 将 CPU 时间快进到下一个任务，并添加任务到任务队列
      time = tasks[tasks.length - 1][0];
      addTask(heap, tasks, time);
    }
  }

  return ans;
};

function addTask(heap, tasks, time) {
  // 将 tasks 中入队时间不快于当前 CPU 时间的任务入队
  while (tasks.length && tasks[tasks.length - 1][0] <= time) {
    heap.enqueue(tasks.pop());
  }
}
xixiao51 commented 2 years ago

Idea

Sort + PriorityQueue

Code

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;

        List<Integer> idx = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            idx.add(i);
        }
        idx.sort(Comparator.comparingInt(o -> tasks[o][0]));

        Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]);
            return Integer.compare(o1[1], o2[1]);
        });

        int[] res = new int[n];
        int k = 0, time = 0;
        for (int i = 0; i < n; i++) {
            if (pq.isEmpty())
                time = Math.max(time, tasks[idx.get(k)][0]);

            while (k < n && tasks[idx.get(k)][0] <= time) {
                pq.offer(new int[]{tasks[idx.get(k)][1], idx.get(k)});
                k++;
            }

            int[] t = pq.poll();
            time += t[0];
            res[i] = t[1];
        }

        return res;
    }
}

Complexity Analysis

wychmod commented 2 years ago

思路

主要思路是要使用堆结构进行排序，小根堆，每次弹出最小的。然后为了方便一开始要进行排序，但是要注意保持原来的数组的下标。

代码

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        tasks.sort()
        curtime = tasks[0][0]
        ans = []
        heap = []
        i = 0
        while i < len(tasks):
            while i<len(tasks) and tasks[i][0] <= curtime:
                task = (tasks[i][2], tasks[i][1])
                heapq.heappush(heap, task)
                i += 1
            cur = heapq.heappop(heap)
            curtime += cur[0]
            ans.append(cur[1])
            if i<len(tasks) and  not heap:
                curtime = max(tasks[i][0], curtime)
        while heap:
            cur = heapq.heappop(heap)
            ans.append(cur[1])
        return ans

复杂度分析

时间复杂度Onlogn 空间复杂度On

xiayuhui231 commented 2 years ago

题目

单线程 https://leetcode-cn.com/problems/single-threaded-cpu/submissions/

代码

class Solution {
public:
    using P = pair<int,int>;
    vector<int> getOrder(vector<vector<int>>& tasks) {
        vector<int> res;
        auto comp = [&](const P& a, const P& b){
            if(a.first != b.first) return a.first > b.first;
            else return a.second > b.second;
        };
        priority_queue<P,vector<P>,decltype(comp)> pq(comp);

        int cnt = 0, n = tasks.size(), idx = 0, i = 0;
        long long t = 1;
        for(auto& vec: tasks){
            vec.push_back(i++);
        }
        sort(tasks.begin(),tasks.end());
        while(cnt < n){
            bool exec = false;
            while(idx < n){
                if(tasks[idx][0] <= t){
                    exec = true;
                    pq.push(P(tasks[idx][1],tasks[idx][2]));
                    ++idx;
                }
                else{
                    if(!exec && pq.empty()){
                        t = tasks[idx][0];
                    }
                    break;
                }
            }

            if(pq.empty()) continue;
            auto curr = pq.top();
            pq.pop();
            res.push_back(curr.second);
            t += curr.first;
            ++cnt;
        }

        return res;

    }
};

复杂度

时间复杂度:O(nlogn) 空间复杂度:O(n)

hyh331 commented 2 years ago

Day33 思路

  1. 两个优先队列，taskq和readyq,taskq用enqueTime排序，ready用processTime排序
  2. 所有任务进入taskq,到了处理时间的进入readyq。 
    class Solution {
public:
vector<int> getOrder(vector<vector<int>>& tasks) {
    //两个优先队列，taskq和readyq,taskq用enqueTime排序，ready用processTime排序
    //所有任务进入taskq,到了处理时间的进入readyq。
    priority_queue<pair<int,int>, vector<pair<int, int>>, greater<> > taskq;
    priority_queue<pair<int,int>, vector<pair<int, int>>, greater<> > readyq;
    //tasks共有n项任务
    int n=tasks.size();
    //将tasks中所有的第一个元素放入taskq的容器中，taskq=[[1,0],[2,1],[3,2],[4,3]],
    for(int i=0; i < n; i++){
        taskq.emplace(tasks[i][0], i);
    }
    vector<int> ans;
    //时间戳变量
    long ts=0;
    for(int i = 0; i < n; i++){
        if(readyq.empty() && ts<taskq.top().first){
            ts = taskq.top().first;
        }
        //将所有<=ts的任务放入readyq队列
        while(!taskq.empty() && taskq.top().first <= ts){
            int i =taskq.top().second;
            taskq.pop();
            readyq.emplace(tasks[i][1] , i);
        }
        //选择处理时间最小的任务 auto&& 右值引用，没看懂
        auto&& [t, index]=readyq.top();
        ts+=t;
        ans.push_back(index);
        readyq.pop();
    }
    return ans;
}
};

    复杂度分析

    • 时间复杂度：O(nlogn)
    • 空间复杂度：O(n)
maybetoffee commented 2 years ago 
class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        // 把原始索引也添加上，方便后面排序用
        ArrayList<int[]> triples = new ArrayList<>();
        for (int i = 0; i < tasks.length; i++) {
            triples.add(new int[]{tasks[i][0], tasks[i][1], i});
        }
        // 数组先按照任务的开始时间排序
        triples.sort((a, b) -> {
            return a[0] - b[0];
        });

        // 按照任务的处理时间排序，如果处理时间相同，按照原始索引排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[1] != b[1]) {
                // 比较处理时间
                return a[1] - b[1];
            }
            // 比较原始索引
            return a[2] - b[2];
        });

        ArrayList<Integer> res = new ArrayList<>();
        // 记录完成任务的时间线
        int now = 0;
        int i = 0;
        while (res.size() < n) {
            if (!pq.isEmpty()) {
                // 完成队列中的一个任务
                int[] triple = pq.poll();
                res.add(triple[2]);
                // 每完成一个任务，就要推进时间线
                now += triple[1];
            } else if (i < n && triples.get(i)[0] > now) {
                // 队列为空可能因为还没到开始时间，
                // 直接把时间线推进到最近任务的开始时间
                now = triples.get(i)[0];
            }

            // 由于时间线的推进，会产生可以开始执行的任务
            for (; i < n && triples.get(i)[0] <= now; i++) {
                pq.offer(triples.get(i));
            }
        }

        // Java 语言特性，将 List 转化成 int[] 格式
        int[] arr = new int[n];
        for (int j = 0; j < n; j++) {
            arr[j] = res.get(j);
        }
        return arr;
    }
}
miss1 commented 2 years ago

思路

堆。先将index添加到tasks中，再将tasks按enqueueTime排序。遍历tasks，将enqueueTime小于当前时间的任务添加到堆中等待执行；取出堆中第一个task执行，更新执行完之后的当前时间。

代码

var getOrder = function(tasks) {
  tasks = tasks.map((val, index) => [...val, index]);
  tasks.sort((a, b) => b[0] - a[0]);
  let queue = new MinPriorityQueue({priority: (val) => (10 ** 5) * val[1] + val[2]});
  let res = [], time = tasks[tasks.length - 1][0];
  while (tasks.length > 0 || queue.size() > 0) {
    while (tasks.length > 0 && time >= tasks[tasks.length - 1][0]) queue.enqueue(tasks.pop());
    if (queue.size() > 0) {
      let current = queue.dequeue().element;
      time = time + current[1];
      res.push(current[2]);
    } else if (tasks.length > 0) {
      time = tasks[tasks.length - 1][0];
    }
  }
  return res;
};

复杂度

time: O(nlog(n))

space: O(n)

zhishinaigai commented 2 years ago

思路

排序+优先队列

代码

class Solution {
private:
    using PII=pair<int,int>;
    using LL=long long;
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n=tasks.size();
        vector<int> indices(n);
        iota(indices.begin(),indices.end(),0);
        sort(indices.begin(),indices.end(),[&](int i,int j){
            return tasks[i][0]<tasks[j][0];
        });
        vector<int> ans;
        priority_queue<PII,vector<PII>,greater<PII>> q;
        LL timestamp=0;
        int ptr=0;
        for(int i=0;i<n;++i){
            if(q.empty()) timestamp=max(timestamp,(LL)tasks[indices[ptr]][0]);
            while(ptr<n && tasks[indices[ptr]][0]<=timestamp){
                q.emplace(tasks[indices[ptr]][1],indices[ptr]);
                ++ptr;
            }
            auto&& [process,index]=q.top();
            timestamp+=process;
            ans.push_back(index);
            q.pop();
        }
        return ans;
    }
};
KelvinG-LGTM commented 2 years ago

思路

纯模拟. 超时

代码

# 超时
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        start_time = min(i[0] for i in tasks)
        finished = 0
        start_dic = defaultdict(list) # start_time : idx 
        for idx, task in enumerate(tasks): 
            start_dic[task[0]].append(idx)
        # print(start_dic)
        cur_time = end_time = start_time
        queue = []  # indexes
        idle = True
        res = []
        while finished < len(tasks): 
            # 1. Prepare task queue
            queue.extend(start_dic[cur_time])
            # 2. If idle. 
            idle = (cur_time == end_time)
            if idle: 
                queue.sort(key=lambda idx: (tasks[idx][1], idx))  # 相同值按照tasks里面的index排序. 
                task_idx = queue.pop(0)
                res.append(task_idx)
                end_time = cur_time + tasks[task_idx][1]
                finished += 1
            cur_time += 1
        return res
# 使用heap
def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        indices = list(range(n))
        indices.sort(key=lambda x: tasks[x][0])

        ans = list()
        # 优先队列
        q = list()
        # 时间戳
        timestamp = 0
        # 数组上遍历的指针
        ptr = 0

        for i in range(n):
            # 如果没有可以执行的任务，直接快进
            if not q:
                timestamp = max(timestamp, tasks[indices[ptr]][0])
            # 将所有小于等于时间戳的任务放入优先队列
            while ptr < n and tasks[indices[ptr]][0] <= timestamp:
                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))
                ptr += 1
            # 选择处理时间最小的任务
            process, index = heapq.heappop(q)
            timestamp += process
            ans.append(index)

        return ans

复杂度分析

时间复杂度

空间复杂度

mo660 commented 2 years ago 
class Solution {
private:
    using PII = pair<int, int>;
    using LL = long long;

public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n = tasks.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) {
            return tasks[i][0] < tasks[j][0];
        });

        vector<int> ans;
        // 优先队列
        priority_queue<PII, vector<PII>, greater<PII>> q;
        // 时间戳
        LL timestamp = 0;
        // 数组上遍历的指针
        int ptr = 0;

        for (int i = 0; i < n; ++i) {
            // 如果没有可以执行的任务，直接快进
            if (q.empty()) {
                timestamp = max(timestamp, (LL)tasks[indices[ptr]][0]);
            }
            // 将所有小于等于时间戳的任务放入优先队列
            while (ptr < n && tasks[indices[ptr]][0] <= timestamp) {
                q.emplace(tasks[indices[ptr]][1], indices[ptr]);
                ++ptr;
            }
            // 选择处理时间最小的任务
            auto&& [process, index] = q.top();
            timestamp += process;
            ans.push_back(index);
            q.pop();
        }

        return ans;
    }
};
LQyt2012 commented 2 years ago

思路

堆排序，关键字1是任务执行时间，关键字2任务序号。

代码

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        indices = list(range(n))
        indices.sort(key=lambda x: tasks[x][0])

        ans = list()
        # 优先队列
        q = list()
        # 时间戳
        timestamp = 0
        # 数组上遍历的指针
        ptr = 0

        for i in range(n):
            # 如果没有可以执行的任务，直接快进
            if not q:
                timestamp = max(timestamp, tasks[indices[ptr]][0])
            # 将所有小于等于时间戳的任务放入优先队列
            while ptr < n and tasks[indices[ptr]][0] <= timestamp:
                # 排序的关键字为运行时间优先，其次是任务序号
                heapq.heappush(q, (tasks[indices[ptr]][1], indices[ptr]))
                ptr += 1
            # 选择处理时间最小的任务
            process, index = heapq.heappop(q)
            timestamp += process
            ans.append(index)

        return ans

复杂度分析

时间复杂度：O(NlogN)
空间复杂度：O(N)

zzz607 commented 2 years ago

思路

先按照enqueueTime排序，然后遍历任务数组，针对每个任务，执行下述操作:

  1. 申明一个小顶堆，堆顶元素即为执行时间最短、且下标最小的元素。初始时，将任务数据的第 一个元素加入该堆中。
  2. 从堆中取出一个任务，计算该任务执行结束时间，然后再从排序后的任务数组中取出所有开始 时间小于正在执行的任务的结束时间的任务。重复此步骤

代码

func getOrder(tasks [][]int) []int {
    var ret []int

    var newTasks = make([]*taskMeta, 0, len(tasks))
    for idx, item := range tasks {
        newTasks = append(newTasks, &taskMeta{
            idx:  idx,
            time: item,
        })
    }
    sort.Slice(newTasks, func(i, j int) bool {
        if newTasks[i].time[0] < newTasks[j].time[0] {
            return true
        }
        if newTasks[i].time[0] > newTasks[j].time[0] {
            return false
        }
        if i < j {
            return true
        }
        return false
    })

    taskIdx := 0
    curTime := newTasks[0].time[0]
    heap := newMyHeap()
    for ; taskIdx < len(newTasks); taskIdx++ {
        if curTime != newTasks[taskIdx].time[0] {
            break
        }
        heap.push(&taskMeta{idx: newTasks[taskIdx].idx, time: newTasks[taskIdx].time})
    }

    for heap.len() != 0 {
        cur := heap.delete()
        ret = append(ret, cur.idx)

        curTime += cur.time[1]

        found := false
        for ; taskIdx < len(newTasks); taskIdx++ {
            if newTasks[taskIdx].time[0] <= curTime {
                heap.push(&taskMeta{idx: newTasks[taskIdx].idx, time: newTasks[taskIdx].time})
                found = true
                continue
            }
            break
        }

        if !found && taskIdx != len(newTasks) && heap.len() == 0 {
            // CPU空闲时间
            curTime = newTasks[taskIdx].time[0]
            for ; taskIdx < len(newTasks); taskIdx++ {
                if curTime != newTasks[taskIdx].time[0] {
                    break
                }
                heap.push(&taskMeta{idx: newTasks[taskIdx].idx, time: newTasks[taskIdx].time})
            }
        }
    }

    return ret
}

type taskMeta struct {
    idx int
    time []int
}

type myHeap struct {
    data []*taskMeta
}

func newMyHeap() *myHeap {
    return &myHeap{data: make([]*taskMeta, 0)}
}

func (h *myHeap) push(v *taskMeta) {
    h.data = append(h.data, v)
    h.up()
}

func (h *myHeap) delete() *taskMeta {
    tmp := h.data[0]
    h.swap(0, h.len() - 1)
    h.data = h.data[:h.len() - 1]
    h.down(0)
    return tmp
}

func (h *myHeap) up() {
    last := h.len() - 1
    for {
        parent := h.getParent(last)
        if parent == -1 {
            break
        }

        if !h.less(last, parent) {
            break
        }

        h.swap(last, parent)
        last = parent
    }
}

func (h *myHeap) down(b int) {
    var maxChildValue func(idx int) int
    maxChildValue = func(idx int) int {
        leftChild := h.getLeftChild(idx)
        rightChild := h.getRightChild(idx)
        if rightChild != -1 && leftChild != -1 {
            if h.less(leftChild, rightChild) {
                return leftChild
            }
            return rightChild
        }
        return leftChild
    }

    for {
        child := maxChildValue(b)
        if child == -1 {
            break
        }

        if h.less(b, child) {
            break
        }

        h.swap(b, child)
        b = child
    }
}

func (h *myHeap) getParent(idx int) int {
    if idx == 0 {return -1}
    return (idx - 1) / 2
}

func (h *myHeap) getLeftChild(idx int) int {
    cIdx := 2 * idx + 1
    if cIdx >= h.len() {
        return -1
    }
    return cIdx
}

func (h *myHeap) getRightChild(idx int) int {
    cIdx := 2 * idx + 2
    if cIdx >= h.len() {
        return -1
    }
    return cIdx
}

func (h *myHeap) len() int {
    return len(h.data)
}

func (h *myHeap) swap(i, j int) {
    h.data[i], h.data[j] = h.data[j], h.data[i]
}

func (h *myHeap) less(i, j int) bool {
    if h.data[i].time[1] < h.data[j].time[1] {
        return true
    }
    if h.data[i].time[1] > h.data[j].time[1] {
        return false
    }
    if h.data[i].idx < h.data[j].idx {
        return true
    }
    return false
}

复杂度分析

revisegoal commented 2 years ago

模拟 + 优先队列

class Solution {
    public int[] getOrder(int[][] tasks) {
        int len = tasks.length;
        int[][] tasksWithId = new int[len][3];
        int[] res = new int[len];
        Queue<int[]> queue = new PriorityQueue<>((a, b) ->
            a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
        for (int i = 0; i < len; i++) {
            tasksWithId[i] = new int[]{tasks[i][0], tasks[i][1], i};
        }
        Arrays.sort(tasksWithId, (a, b) -> a[0] - b[0]);
        int time = 0, i = 0, j = 0;
        while (j < len) {
            while (i < len && tasksWithId[i][0] <= time) {
                queue.offer(tasksWithId[i]);
                i++;
            }
            if (queue.isEmpty()) {
                time = tasksWithId[i][0];
                continue;
            }
            int[] toDo = queue.poll();
            time += toDo[1];
            res[j] = toDo[2];
            j++;
        }
        return res;
    }
}
biscuit279 commented 2 years ago

思路

先按照起始时间排序，再用大顶堆维护持续时间

import heapq
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i , task[1]) for i,task in enumerate(tasks)]
        tasks.sort()
        ans = []
        backlog = []
        pos = 0
        time = 0
        for _ in tasks:
            if not backlog:
                time = max(time,tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time :
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1])) # 默认按持续时长排序，大顶
                pos += 1
            d,j = heapq.heappop(backlog)
            ans.append(j)
            time += d
        return ans

时间复杂度：O(nlogn) 空间复杂度:O(n)

houyanlu commented 2 years ago

思路

先将任务的开始时间按从小到大排序，用一个临时数组来存储下标 任务队列用小根堆来存储，根节点就是所需时间最短的任务，每次取出来

如果任务队列为空：就快进到下一个任务的开始时间处，否则将先处理可以加入优先队列的元素，然后从中取出一个执行，处理完时间戳增加此任务的processTime

代码


class Solution {
public:
    vector<int> getOrder(vector<vector<int>>& tasks) {
        int n = tasks.size();
        vector<int> sortTasks;
         for(int i = 0;i < n; i++){
            sortTasks.push_back(i);
        }
        std::sort(sortTasks.begin(), sortTasks.end(), [&](int i, int j){
            return tasks[i][0] < tasks[j][0];
        });

        vector<int> ans;
        // 优先队列， pair<任务处理时间，索引位置>
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        // 时间戳
        long long timestamp = 0;
        int pos = 0;

        for (int i = 0; i < n; ++i) {
            if (q.empty()) {
                timestamp = std::max(timestamp, (long long)tasks[sortTasks[pos]][0]);
            }

            while (pos < n && tasks[sortTasks[pos]][0] <= timestamp) {
                q.push({tasks[sortTasks[pos]][1], sortTasks[pos]});
                ++pos;
            }

            const auto &[processTime, index] = q.top();
            timestamp += processTime;
            ans.push_back(index);
            q.pop();
        }

        return ans;
    }
};

复杂度分析

Orangejuz commented 2 years ago

代码：

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:

        n = len(tasks)
        idx = list(range(n))

        # sort index by enqueue time
        idx.sort(key=lambda x: tasks[x][0])

        ans = []
        queue = []
        time = 0
        ptr = 0
        for i in range(n):
            if not queue:
                time = max(time, tasks[idx[ptr]][0])
            while ptr < n and tasks[idx[ptr]][0] <= time:
                heapq.heappush(queue, (tasks[idx[ptr]][1], idx[ptr]))
                ptr += 1

            p, i = heapq.heappop(queue)
            time += p
            ans.append(i)

        return ans
xil324 commented 2 years ago 
import heapq; 
class Solution(object):
    def getOrder(self, tasks):
        """
        :type tasks: List[List[int]]
        :rtype: List[int]
        """
        #use heap to find the min processing time 
        heap = []; 
        task_list = [(task[0], i, task[1]) for i, task in enumerate (tasks)]; #keeps tracking the index 
        task_list = sorted(task_list, key = lambda x : x[0]) #sort processing time 
        res = []; 
        index = 0; 
        time = 0; 
        for _ in tasks:
            if len(heap) == 0: #if no task, process the next avaliable time 
                time = max(time, task_list[index][0]); 

            while index < len(tasks) and task_list[index][0] <= time:
                heapq.heappush(heap,(task_list[index][2], task_list[index][1])); #choose the shortest processing time first
                index += 1; 
            processing_time, task_index = heapq.heappop(heap); 
            res.append(task_index); 
            time += processing_time; 

        return res; 
#time complexity: sorting takes O(nlogn), heap O(nlogn)
MichaelXi3 commented 2 years ago

Idea

Geek-LX commented 2 years ago

5.3

思路：

代码

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        tasks.sort()
        backlog = []
        time = 0
        ans = []
        pos = 0
        for _ in tasks:
            if not backlog:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans

复杂度分析

令 n 为数组长度。

GaoMinghao commented 2 years ago 
class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        tasks.sort()
        backlog = []
        time = 0
        ans = []
        pos = 0
        for _ in tasks:
            if not backlog:
                time = max(time, tasks[pos][0])
            while pos < len(tasks) and tasks[pos][0] <= time:
                heapq.heappush(backlog, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            d, j = heapq.heappop(backlog)
            time += d
            ans.append(j)
        return ans
JasonHe-WQ commented 2 years ago

思路： 以时间为单位，步进，用list模拟stack，到了对应时间就入栈，然后等cpu处理完了就pop(0)，继续处理 代码：

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        t = copy.deepcopy(tasks)
        stack = []
        ans = []
        time = 0
        doing = 0
        expectTime = 0
        def trans(L:list):
            index = t.index(L)
            return (L[1],index)
        while tasks or stack:
            i = 0
            while i <len(tasks):
                if tasks[i][0]==time:
                    stack.append(tasks[i])
                    tasks.remove(tasks[i])
                else:
                    i += 1           
            if time == expectTime:
                doing = 0              
            if doing ==0:
                stack.sort(key = trans)
                if stack:
                    doing = _, proc = stack.pop(0)
                    expectTime = time + proc
                    ans.append(t.index(doing))
            time += 1
            continue
        return ans
weihaoxie commented 2 years ago

思路

taojin1992 commented 2 years ago 

/*
Time: O(nlogn), n = number of tasks
Space: O(n)

*/

class Solution {
    public int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        int[] order = new int[n];
        int[][] taskInfo = new int[n][3];
        for (int i = 0; i < n; i++) {
            taskInfo[i][0] = i;
            taskInfo[i][1] = tasks[i][0];
            taskInfo[i][2] = tasks[i][1];
        }
        // sort by enqueue time
        Arrays.sort(taskInfo, (a,b)->a[1] - b[1]);

        // pq
        // process time ==, smaller index first; not equal, shorter process time first
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[2] == b[2] ? a[0] - b[0] : a[2] - b[2]);

        int time = 0;
        int resIndex = 0;
        int ti = 0;
        while(resIndex < n) {

            while(ti < n && taskInfo[ti][1] <= time) {
                pq.offer(taskInfo[ti++]);

            }

            if(pq.isEmpty()) {
                time = taskInfo[ti][1];
                continue;
            }
            int[] bestFit = pq.poll();
            order[resIndex++] = bestFit[0];
            time += bestFit[2];
        }

        return order;
    }
}
AConcert commented 2 years ago 
const getOrder = function (tasks) {
  const queue = new MinPriorityQueue()
  tasks = tasks.map((task, index) => ({
    index,
    start: task[0],
    time: task[1]
  }))
  tasks.sort((a, b) => b.start - a.start)
  const answer = []
  let time = 0
  while (tasks.length > 0 || !queue.isEmpty()) {

    if (queue.isEmpty() && tasks[tasks.length - 1].start > time) {
      time = tasks[tasks.length - 1].start
    }

    while (tasks.length > 0) {
      if (tasks[tasks.length -1].start <= time) {
        const task = tasks.pop()
        queue.enqueue(task, task.time * 100000 + task.index)
      } else {
        break
      }
    }

    const { element: task } = queue.dequeue()
    time += task.time
    answer.push(task.index)
  }
  return answer
}
sallyrubyjade commented 2 years ago

代码


/**
 * @param {number[][]} tasks
 * @return {number[]}
 */
const getOrder = function (tasks) {
    const queue = new MinPriorityQueue()
    tasks = tasks.map((task, index) => ({
        index,
        start: task[0],
        time: task[1]
    }))
    tasks.sort((a, b) => b.start - a.start)
    const answer = []
    let time = 0
    while (tasks.length > 0 || !queue.isEmpty()) {
        // 队列为空，且没有任务能加入队列，直接跳过时间
        if (queue.isEmpty() && tasks[tasks.length - 1].start > time) {
        time = tasks[tasks.length - 1].start
    }

    // 向队列中加入可执行任务
    while (tasks.length > 0) {
        if (tasks[tasks.length -1].start <= time) {
            const task = tasks.pop()
            queue.enqueue(task, task.time * 100000 + task.index)
        } else {
            break
        }
    }

    // 执行任务
    const { element: task } = queue.dequeue()
        time += task.time
        answer.push(task.index)
    }

    return answer
}
linjunhe commented 2 years ago

思路

  1. 按照enqueueTime对任务升序排序
  2. 把enqueueTime小于当前时间戳的任务加入待执行列表waiting
  3. 从waiting里找processingTime最小的执行

Code

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        n = len(tasks)
        # (enqueueTime, taskIndex, processingTime)
        tasks = [(task[0], i, task[1]) for i, task in enumerate(tasks)]
        # 将tasks中所有任务按照enqueueTime升序排序
        tasks.sort()

        waiting = []
        time = 0
        ans = []
        pos = 0
        for i in range(n): 
            # 如果队列没有任务，则直接将 time 快进到下一个任务的enqueueTime
            if not waiting:
                time = max(time, tasks[pos][0])

            # enqueueTime小于等于时间戳的task放入等待队列
            while pos< n and tasks[pos][0] <= time:
                heapq.heappush(waiting, (tasks[pos][2], tasks[pos][1]))
                pos += 1
            # 从等待队列中取出一个时间最短的进行处理
            processingTime, taskIndex = heapq.heappop(waiting)
            time += processingTime
            ans.append(taskIndex)
        return ans

复杂度分析