Simple Java solution with comments


  • 0
    V
    public class Solution {
        
        public int scheduleCourse(int[][] courses) {
            // max heap "(x,y) -> y-x" denotes descending order
            PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((x,y) -> y-x);
            // sort courses based on the second column (day to complete)
            Arrays.sort(courses, (a,b) -> a[1] - b[1]);
            
            int coursesTaken = 0;
            int currentDay = 0;
            for(int i=0; i<courses.length; i++) {
                if(currentDay + courses[i][0] <= courses[i][1]) {
                    coursesTaken++;
                    currentDay += courses[i][0];
                    maxHeap.add(courses[i][0]);
                } else if(maxHeap.peek() > courses[i][0]) {
                    if(currentDay + courses[i][0] - maxHeap.peek() <= courses[i][1]) {
                        //System.out.println("couldn't take, so remove max then add this: "+courses[i][0]+","+ courses[i][1]);
                        //System.out.println("max days course so far : "+maxHeap.peek());
                        currentDay = currentDay - maxHeap.poll() + courses[i][0];
                        maxHeap.add(courses[i][0]);
                    }
                }
            }
            return coursesTaken;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.