630. Course Schedule III

 一刷 06/2022

Version #1 Max Heap

思路就是按顺序安排课程，如果发现不能安排的，就取消之前一个用时最长且大于当前课程时间的课

Time O(NlogN)

Space O(N)

Runtime: 43 ms, faster than 88.70% of Java online submissions for Course Schedule III.

Memory Usage: 74.9 MB, less than 18.52% of Java online submissions for Course Schedule III.

class Solution {

    public int scheduleCourse(int[][] courses) {

        if (courses == null || courses.length == 0) {

            return 0;

        }

        // Sort courses by their end date

        Arrays.sort(courses, (a, b) -> a[1] - b[1]);

        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        int time = 0;

        int cnt = 0;

        for (int[] course : courses) {

            // check if current course can fit into current time

            if (time + course[0] > course[1]) {

                // try to replace with the course with max duration

                if (maxHeap.isEmpty() || maxHeap.peek() <= course[0]) {

                    continue;

                }

                time -= maxHeap.poll();

                cnt--;

            }

            time += course[0];

            maxHeap.offer(course[0]);

            cnt++;

        }

        return cnt;

    }

}