Hard

题目描述

这里有 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 <= 10^4
  • 1 <= durationi, lastDayi <= 10^4

解题思路

这道题是一个经典的贪心算法问题。核心思想是：按照截止时间排序，然后用最大堆来维护已选课程的持续时间。

算法思路：

  1. 预处理：首先按照课程的截止时间（lastDay）对所有课程进行升序排序。这样可以确保我们按照"紧急程度"处理课程。

  2. 贪心选择：遍历排序后的课程，对于每个课程：

    • 如果加入当前课程后总时间不超过截止时间，直接加入
    • 如果超过截止时间，检查当前课程是否比已选课程中持续时间最长的课程更短
    • 如果是，则替换掉持续时间最长的课程

  3. 数据结构：使用最大堆（优先队列）来维护已选课程的持续时间，这样可以快速找到并移除持续时间最长的课程。

为什么这个策略是正确的？

  • 按截止时间排序确保了我们优先处理"更紧急"的课程
  • 当无法直接添加新课程时，用更短的课程替换更长的课程不会违反任何约束，且可能为后续课程腾出时间
  • 这种"反悔"机制最大化了我们能选择的课程数量

推荐解法：贪心 + 最大堆，时间复杂度O(n log n)，是最优解法。

代码实现

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        // 按截止时间排序
        sort(courses.begin(), courses.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        priority_queue<int> pq; // 最大堆，存储已选课程的持续时间
        int totalTime = 0;
        
        for (auto& course : courses) {
            int duration = course[0];
            int lastDay = course[1];
            
            if (totalTime + duration <= lastDay) {
                // 可以直接添加这门课
                pq.push(duration);
                totalTime += duration;
            } else if (!pq.empty() && pq.top() > duration) {
                // 用当前课程替换持续时间最长的课程
                totalTime -= pq.top();
                pq.pop();
                pq.push(duration);
                totalTime += duration;
            }
        }
        
        return pq.size();
    }
};

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        import heapq
        
        # 按截止时间排序
        courses.sort(key=lambda x: x[1])
        
        max_heap = []  # 使用负数模拟最大堆
        total_time = 0
        
        for duration, last_day in courses:
            if total_time + duration <= last_day:
                # 可以直接添加这门课
                heapq.heappush(max_heap, -duration)
                total_time += duration
            elif max_heap and -max_heap[0] > duration:
                # 用当前课程替换持续时间最长的课程
                longest = -heapq.heappop(max_heap)
                total_time -= longest
                heapq.heappush(max_heap, -duration)
                total_time += duration
        
        return len(max_heap)

public class Solution {
    public int ScheduleCourse(int[][] courses) {
        // 按截止时间排序
        Array.Sort(courses, (a, b) => a[1].CompareTo(b[1]));
        
        var maxHeap = new PriorityQueue<int, int>();
        int totalTime = 0;
        
        foreach (var course in courses) {
            int duration = course[0];
            int lastDay = course[1];
            
            if (totalTime + duration <= lastDay) {
                // 可以直接添加这门课
                maxHeap.Enqueue(duration, -duration); // 使用负优先级模拟最大堆
                totalTime += duration;
            } else if (maxHeap.Count > 0 && maxHeap.Peek() > duration) {
                // 用当前课程替换持续时间最长的课程
                int longest = maxHeap.Dequeue();
                totalTime -= longest;
                maxHeap.Enqueue(duration, -duration);
                totalTime += duration;
            }
        }
        
        return maxHeap.Count;
    }
}

var scheduleCourse = function(courses) {
    courses.sort((a, b) => a[1] - b[1]);
    
    const maxHeap = [];
    let currentTime = 0;
    
    for (const [duration, lastDay] of courses) {
        currentTime += duration;
        maxHeap.push(duration);
        maxHeap.sort((a, b) => b - a);
        
        if (currentTime > lastDay) {
            currentTime -= maxHeap.shift();
        }
    }
    
    return maxHeap.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)排序需要O(n log n)，每个课程最多进出堆一次，堆操作为O(log n)
空间复杂度O(n)最大堆最多存储n个课程的持续时间

相关题目