Skip to content

1834. Single-Threaded CPU 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  vector<int> getOrder(vector<vector<int>>& tasks) {
    const int n = tasks.size();

    // Add index information.
    for (int i = 0; i < tasks.size(); ++i)
      tasks[i].push_back(i);

    vector<int> ans;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    int i = 0;      // tasks' index
    long time = 0;  // the current time

    ranges::sort(tasks);
    while (i < n || !minHeap.empty()) {
      if (minHeap.empty())
        time = max(time, static_cast<long>(tasks[i][0]));
      while (i < n && time >= tasks[i][0]) {
        minHeap.emplace(tasks[i][1], tasks[i][2]);
        ++i;
      }
      const auto [procTime, index] = minHeap.top();
      minHeap.pop();
      time += procTime;
      ans.push_back(index);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class T {
  public int procTime;
  public int index;

  public T(int procTime, int index) {
    this.procTime = procTime;
    this.index = index;
  }
}

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

    for (int i = 0; i < n; ++i) {
      A[i][0] = tasks[i][0];
      A[i][1] = tasks[i][1];
      A[i][2] = i;
    }

    int[] ans = new int[n];
    int ansIndex = 0;
    Queue<T> minHeap = new PriorityQueue<>(
        (a, b) -> a.procTime == b.procTime ? a.index - b.index : a.procTime - b.procTime);
    int i = 0;     // tasks' index
    long time = 0; // the current time

    Arrays.sort(A, Comparator.comparing(a -> a[0]));

    while (i < n || !minHeap.isEmpty()) {
      if (minHeap.isEmpty())
        time = Math.max(time, (long) A[i][0]);
      while (i < n && time >= (long) A[i][0]) {
        minHeap.offer(new T(A[i][1], A[i][2]));
        ++i;
      }
      final int procTime = minHeap.peek().procTime;
      final int index = minHeap.poll().index;
      time += procTime;
      ans[ansIndex++] = index;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def getOrder(self, tasks: List[List[int]]) -> List[int]:
    n = len(tasks)
    A = [[*task, i] for i, task in enumerate(tasks)]
    ans = []
    minHeap = []
    i = 0  # tasks' index
    time = 0  # the current time

    A.sort()

    while i < n or minHeap:
      if not minHeap:
        time = max(time, A[i][0])
      while i < n and time >= A[i][0]:
        heapq.heappush(minHeap, (A[i][1], A[i][2]))
        i += 1
      procTime, index = heapq.heappop(minHeap)
      time += procTime
      ans.append(index)

    return ans