05 August 2008
给n个标记为0到n-1的任务，用一个二维整数数组tasks表示，其中tasks[i] = [enqueueTimei, processingTimei]表示第i个任务将在 enqueueTimei 处可供处理，并将花费 processingTimei 完成处理。
有一个单线程 CPU，它一次最多可以处理一个任务，并且将按以下方式运行：
如果 CPU 处于空闲状态并且没有可用的任务可处理，则 CPU 保持空闲状态。
如果 CPU 空闲且有可用任务，则 CPU 将选择处理时间最短的一个。如果多个任务的处理时间最短，它会选择索引最小的任务。
一旦一个任务启动，CPU 就会不停地处理整个任务。
CPU 可以完成一项任务，然后立即启动一个新任务。
返回 CPU 处理任务的顺序。
Treeset
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
47
48
49
50
51
52
53
class Solution {
public int[] getOrder(int[][] tasks) {
int[][] taskMatrix = new int[tasks.length][];
// to store the index of taksk along with other values;
for (int i = 0; i < tasks.length; ++i) {
taskMatrix[i] = new int[]{tasks[i][0], tasks[i][1], i};
}
Arrays.sort(taskMatrix, (a, b) -> a[0] - b[0]); // sort array on the basis of enqueue time
Comparator<int[]> sortOnTimeToComplete = new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[1] != b[1]) {
return a[1] - b[1]; // when time to complete is not same
} else if (a[2] != b[2]) {
return a[2] - b[2]; // when time to complete is same, then consider the task which came first
} else {
return -1;
}
}
};
TreeSet<int[]> taskSet = new TreeSet<int[]>(sortOnTimeToComplete);
int i = 0;
int[] result = new int[tasks.length];
int index = 0;
int nextAvailableTime = 0;
while (i < taskMatrix.length) {
while (i < tasks.length && taskMatrix[i][0] <= nextAvailableTime) {
taskSet.add(taskMatrix[i]);
i++;
}
if (!taskSet.isEmpty()) {
int[] easyTask = taskSet.pollFirst();
result[index++] = easyTask[2];
nextAvailableTime = nextAvailableTime + easyTask[1];
} else {
nextAvailableTime = taskMatrix[i][0];
}
}
while (!taskSet.isEmpty()) {
int[] easyTask = taskSet.pollFirst();
result[index++] = easyTask[2];
}
return result;
}
}
Two heaps
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
47
48
49
50
51
52
53
class Solution {
public int[] getOrder(int[][] tasks) {
int c[] = new int[tasks.length];
int z = 0;
PriorityQueue<node> res = new PriorityQueue<>((a, b) -> {
if (a.a != b.a) return a.a - b.a;
return a.b - b.b;
});
PriorityQueue<node> str = new PriorityQueue<>((a, b) -> {
if (a.b == b.b) return a.pos - b.pos;
return a.b - b.b;
});
for (int i = 0; i < tasks.length; i++) {
node a = new node();
a.a = tasks[i][0];
a.b = tasks[i][1];
a.pos = i;
res.add(a);
}
int d = -1;
while (!res.isEmpty() || !str.isEmpty()) {
if (str.isEmpty()) {
node cur = res.poll();
d = cur.a;
d += cur.b;
c[z++] = cur.pos;
while (!res.isEmpty() && d >= res.peek().a) {
str.add(res.poll());
}
} else {
node cur = str.poll();
c[z++] = cur.pos;
d += cur.b;
while (!res.isEmpty() && d >= res.peek().a) {
str.add(res.poll());
}
}
}
return c;
}
}
class node {
int a;
int b;
int pos;
}
minHeap
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
public int[] getOrder(int[][] tasks) {
if (tasks == null || tasks.length == 0) {
return new int[0];
}
PriorityQueue<Task> incomingTasks = new PriorityQueue<>(new IncomingTasksComparator());
for (int i = 0; i < tasks.length; i++) {
incomingTasks.offer(new Task(i, tasks[i][0], tasks[i][1]));
}
int[] result = new int[tasks.length];
int resultIndex = 0;
int time = 0;
PriorityQueue<Task> queue = new PriorityQueue<>(new QueueComparator());
while (!incomingTasks.isEmpty() || !queue.isEmpty()) {
// if queue is empty, cpu is idle. jump to next non-idle time
if (queue.isEmpty()) {
time = incomingTasks.peek().enqueueTime;
// add all the tasks whose enqueueTime < current time to the queue
addEligibleTaskToQueue(incomingTasks, queue, time);
}
// get next task to execute
Task current = queue.poll();
// process the task
result[resultIndex++] = current.index;
time += current.processingTime;
// add all the tasks whose enqueueTime < current time to the queue
addEligibleTaskToQueue(incomingTasks, queue, time);
}
return result;
}
private void addEligibleTaskToQueue(PriorityQueue<Task> incomingTasks, PriorityQueue<Task> queue, int time) {
while (incomingTasks.peek() != null && incomingTasks.peek().enqueueTime <= time) {
queue.offer(incomingTasks.poll());
}
}
}
class Task {
int index;
int enqueueTime;
int processingTime;
public Task(int index, int enqueueTime, int processingTime) {
this.index = index;
this.enqueueTime = enqueueTime;
this.processingTime = processingTime;
}
}
class IncomingTasksComparator implements Comparator<Task> {
@Override
public int compare(Task t1, Task t2) {
return t1.enqueueTime - t2.enqueueTime;
}
}
class QueueComparator implements Comparator<Task> {
@Override
public int compare(Task t1, Task t2) {
if (t1.processingTime == t2.processingTime) {
return t1.index - t2.index;
}
return t1.processingTime - t2.processingTime;
}
}