[数据结构与算法]力扣每日一题2021-12-14困难题：课程表III

630.课程表III

题目描述

课程表III

思路

贪心

按结束时间排序，可以保证先考虑加入先结束的课程。
在课程塞满时，用当前的（如果耗时更短）替换耗时最长的那一个。

Python实现

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        pq, t = [], 0
        for duration, lastDay in sorted(courses, key=lambda x:x[1]):
            if t + duration > lastDay and pq and -pq[0] > duration:
                t += heapq.heappop(pq)
            if t + duration <= lastDay:
                heapq.heappush(pq, -duration)
                t += duration
        return len(pq)

Java实现

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a,b) -> (a[1] - b[1]));
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->(b-a));
        int t = 0;
        for(int[] course: courses){
            if(t + course[0] > course[1] && pq.size() > 0 && pq.peek() > course[0])
                t -= pq.poll();
            if(t + course[0] <= course[1]){
                t += course[0];
                pq.offer(course[0]);
            }
        }
        return pq.size();
    }
}