Leetcode 1834 - Loading...
Thinking Steps -
- We need a Priority Queue - Key is job length+original index
- Need to pre-sort by start time, and keep track of original index
- Arranging the while loops to populate and read off the heap correctly
class Solution {
public int[] getOrder(int[][] tasks) {
PriorityQueue<TaskItem> minHeap = new PriorityQueue<>();
int[][] tasks2 = new int[tasks.length][3];
for (int i=0; i<tasks.length; i++)
{
tasks2[i][0] = tasks[i][0];
tasks2[i][1] = tasks[i][1];
tasks2[i][2] = i;
}
tasks = tasks2;
Arrays.sort(tasks, new Comparator<int[]>()
{ @Override
public int compare(int[] one, int[] another)
{
return Integer.compare(one[0], another[0]);
}
});
int[] output = new int[tasks.length];
int oi = 0;
int clock = tasks[0][0];
int i = 0;
while ((!minHeap.isEmpty()) || (i<tasks.length))
{
while (i<tasks.length && tasks[i][0] <= clock)
{
minHeap.add(new TaskItem(tasks[i][2], tasks[i][1]));
i++;
}
if (minHeap.isEmpty())
{
clock = tasks[i][0];
}
else
{
TaskItem eligible = minHeap.poll();
output[oi++] = eligible.index;
clock += eligible.length;
}
}
return output;
}
}
public class TaskItem implements Comparable
{
public int index;
public int length;
public TaskItem(int index, int length)
{
this.index = index;
this.length = length;
}
@Override
public int compareTo(Object oth)
{
TaskItem other = (TaskItem)oth;
if (this.length == other.length) return Integer.compare(this.index, other.index);
return Integer.compare(this.length, other.length);
}
}
Time Complexity : O(n log(n))
Space Complexity : O(n)
Suggestions and Improvements are most welcome.
There is a good explanation of the logic at - Krammer's blog
Thanks and Have a Great Weekend !