630. Course Schedule III 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, Comparator.comparingInt(o -> o[1])); // 把 lastDay 大的课程放最后上，我们先上 lastDay 小的课程，以尽量上更多的课程
        Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o2, o1)); // 大顶堆，堆顶为上过的耗时最久的课程

        int day = 0;
        for (int[] course : courses) {
            int duration = course[0], lastDay = course[1];
            if (day + duration <= lastDay) {
                day += duration;
                queue.offer(duration);
            } else if (!queue.isEmpty() && duration < queue.peek()) { // 当前课程比之前的课程耗时短，不上之前的课程了，上现在的课程
                day -= queue.poll();
                day += duration;
                queue.offer(duration);
            }
        }

        return queue.size();
    }
}

References

630. Course Schedule III