我给大家讲道题吧。# JobHunting - 待字闺中
D*0
1 楼
course-schedule-iii
题目的意思就是说：
给定一堆 长度为2的二维数组。
数组表示：[这个课程所需时间， 这个课程的截止日期]
问，最多能上多少门课。
解题用了贪心法：
首先对把所有的课程按照截止日期排序， 截止日期早的放前面。
然后建立一个最大堆。 堆顶是耗时间最长的课程。
维持一个变量 time 用来记录当前所有的课程总共消耗了多少时间。
如果当先总共消耗的时间 超过了当前课程的截止日期。 我们就把当前选了的课程中
最费时间的课程退掉。
最后堆里有多少门课，就是我们最多能选的课程数量。
代码如下：
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses, (n1, n2) -> n1[1]- n2[1]);
PriorityQueue pq = new PriorityQueue<>((a,b) -> b[0]-a[0]);
int time = 0;
for (int[] course : courses) {
time += course[0];
pq.offer(course);
if (time > course[1]) {
time -= pq.poll()[0];
}
}
return pq.size();
}
}
题目的意思就是说：
给定一堆 长度为2的二维数组。
数组表示：[这个课程所需时间， 这个课程的截止日期]
问，最多能上多少门课。
解题用了贪心法：
首先对把所有的课程按照截止日期排序， 截止日期早的放前面。
然后建立一个最大堆。 堆顶是耗时间最长的课程。
维持一个变量 time 用来记录当前所有的课程总共消耗了多少时间。
如果当先总共消耗的时间 超过了当前课程的截止日期。 我们就把当前选了的课程中
最费时间的课程退掉。
最后堆里有多少门课，就是我们最多能选的课程数量。
代码如下：
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses, (n1, n2) -> n1[1]- n2[1]);
PriorityQueue
int time = 0;
for (int[] course : courses) {
time += course[0];
pq.offer(course);
if (time > course[1]) {
time -= pq.poll()[0];
}
}
return pq.size();
}
}
