class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
}
};
630. 课程表 III
这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
示例 1：
输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出：3 解释： 这里一共有 4 门课程，但是你最多可以修 3 门： 首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。 第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。 第三，修第 2 门课，耗时 200 天，在第 1300 天完成。 第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
示例 2：
输入：courses = [[1,2]] 输出：1
示例 3：
输入：courses = [[3,2],[4,3]] 输出：0
提示:
1 <= courses.length <= 1041 <= durationi, lastDayi <= 104原站题解
php 解法, 执行用时: 316 ms, 内存消耗: 32 MB, 提交时间: 2023-09-11 06:14:24
class Solution {
/**
* @param Integer[][] $courses
* @return Integer
*/
function scheduleCourse($courses) {
usort($courses, function ($a, $b) {
return $a[1] - $b[1];
});
$hp = new SplMaxHeap;
$days = 0;
foreach ($courses as $c) {
$days += $c[0];
$hp->insert($c[0]);
if ($days > $c[1]) {
$days -= $hp->extract();
}
}
return $hp->count();
}
}
cpp 解法, 执行用时: 200 ms, 内存消耗: 54.9 MB, 提交时间: 2023-09-10 12:16:37
class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
int duration_time = 0;
sort(courses.begin(), courses.end(), [](const auto &x, const auto &y){
return x[1] < y[1];
});
priority_queue<int> q;
for (int i = 0; i < courses.size(); i++) {
duration_time += courses[i][0];
q.push(courses[i][0]);
while (duration_time > courses[i][1]) {
int duration = q.top();
q.pop();
duration_time -= duration;
}
}
return q.size();
}
};
golang 解法, 执行用时: 108 ms, 内存消耗: 7.8 MB, 提交时间: 2023-09-10 12:16:21
func scheduleCourse(courses [][]int) int {
sort.Slice(courses, func (i, j int) bool {
return courses[i][1] < courses[j][1]
})
pq, t := &Heap{}, 0
for _, course := range courses {
d,l := course[0], course[1]
if t + d > l && pq.Len() > 0 && pq.IntSlice[0] > d {
t -= heap.Pop(pq).(int)
}
if t + d <= l {
t += d
heap.Push(pq, d)
}
}
return pq.Len()
}
type Heap struct {
sort.IntSlice
}
func (h Heap) Less(i, j int) bool {
return h.IntSlice[i] > h.IntSlice[j]
}
func (h *Heap) Swap(i, j int) {
h.IntSlice[i], h.IntSlice[j] = h.IntSlice[j], h.IntSlice[i]
}
func (h *Heap) Push(x interface{}) {
h.IntSlice = append(h.IntSlice, x.(int))
}
func (h *Heap) Pop() interface{} {
a := h.IntSlice
x := a[len(a) - 1]
h.IntSlice = a[:len(a) - 1]
return x
}
java 解法, 执行用时: 30 ms, 内存消耗: 52.9 MB, 提交时间: 2023-09-10 12:14:35
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();
}
}
python3 解法, 执行用时: 112 ms, 内存消耗: 20.3 MB, 提交时间: 2023-09-10 12:14:21
'''
按结束时间排序，可以保证我们优先考虑加入先结束的课程。 在课程塞满的时候，
用当前的(如果耗时更短)替换耗时最长的那一个(所以使用优先队列维护时长)，
这样做的意义在于我们用更少的时间完成了相同数量的课程，
可以保证后面加入更多课程且不可能比原来的方案的课程少。
'''
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)