While trying to solve this question at stack overflow, I ran into a weird problem: My solution was the same as this solution, except it used a PriorityQueue<List> instead of PriorityQueue<int[]>.
I tried copying the solution from the link above and only modifying it to use a PriorityQueue<List>, and it still failed! Not sure what am I missing here. I thought it could be related to PriorityQueue internal implementation but could find any explanation. Can someone please assist?
Here is the solution after my modifications:
public int[] getOrder(int[][] tasks) {
int n = tasks.length;
// make a new tasks array that contains the index as well
List<List<Integer>> extendedTask = new LinkedList<>();
for(int i = 0; i < tasks.length; i++) {
extendedTask.add(Stream.of(i, tasks[i][0], tasks[i][1]).collect(Collectors.toList()));
}
// first sort the newly create array on the basis of enqueTime
extendedTask.sort((a, b) -> a.get(1) - b.get(1));
// PQ definitoin
PriorityQueue<List<Integer>> pq = new PriorityQueue<List<Integer>>((a,b) -> a.get(2) == b.get(2) ? a.get(0) - b.get(0) : a.get(2) - b.get(2));
// result array and its idx
int[] res = new int[tasks.length];
int idx = 0;
// current time and its index
long currentTime = 0;
int currentTimeIdx = 0;
// until we get all the tasks done
while(idx < n) {
while(currentTimeIdx < n && extendedTask.get(currentTimeIdx).get(1) <= currentTime) { // push all the sorted(in order of enqueTime) tasks if there startTime (enqueTime) is LESS THAN or EQUAL to Current time
pq.offer(extendedTask.get(currentTimeIdx++));
}
if(pq.isEmpty()) { // if there is no task in PQ, update the the currentTime to next task and continue
currentTime = extendedTask.get(currentTimeIdx).get(1);
continue;
}
// get the result and update the currentTime
List<Integer> curr = pq.poll();
res[idx++] = curr.get(0);
currentTime += curr.get(2);
}
return res;
}
}