OJ练习第168题——课程表 III

课程表 III

力扣链接：630. 课程表 III

题目描述

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例

解题思路

优先队列+贪心算法
先将课程按照截止日期进行排序，使用优先队列依次遍历。

Java代码

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b) -> b - a);
        int total = 0;
        for(int[] c : courses) {
            int ti = c[0], di = c[1];
            if(total + ti <= di) {
                total += ti;
                q.offer(ti);
            }else if(!q.isEmpty() && q.peek() > ti) {
                total -= q.poll() - ti;
                q.offer(ti);
            }
        }
        return q.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18