0

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;
    }
}
yoel
  • 9
  • 1
  • 2
    `a.get(2) == b.get(2)` should be `a.get(2).equals(b.get(2))`. It is possible for two different Integer objects to represent the same numeric value. – VGR Jun 28 '22 at 06:25
  • 'Failed' is not a problem description. Try again. – user207421 Jun 28 '22 at 08:10

0 Answers0