630.Class ScheduleIII

2024-01-01

字数统计: 580字 | 阅读时长: 2min

topic：

Thought：

思路来自于宫水三叶ofgreedy + Priority queue，

first，We sort them according to the end of the course。The purpose of doing this is to try every course，See if it can adapt to our timetable。
becausePythonofheapqThe default is a minimum pile，So when we join a course，我们使用其持续时间of负数，从而使得堆顶部始终是持续时间最长ofcourse。
When you traverse each course，尝试把它加入到我们of日程中。but，如果我们发现加入该course后总时间超过了该courseof结束时间，那么我们需要从我们of日程中去掉一个course，最好去掉那个持续时间最长ofcourse，because这将释放出最多of时间，This is why use a maximum pile。
sum += heapq.heappop(q)
Java中ofArrays.sort(courses, (a,b)->a[1]-b[1]); Equivalent toPython中ofcourses.sort(key=lambda x: x[1])

The original text is quoted below，About why you usegreedy：

topic是要我们构造出一种可行of排列，排列中每个courseof实际结束时间满足「The latest time」Require，
求可行排序of最大长度（每个course对答案of贡献都是 1）。
This is easy to guide us「Generalized backpack」Think：simply put，For a certain item（course）For，Different costs under different conditions，
At the timeline `[1,courses[i][1]−courses[i][0]]` The item can be selected，The cost is its duration，
在比该范围大of数轴上无法被选，Cost is infinite。因此某一段特定of时间轴上，问题可抽象成有条件限制of组合优化问题。
Because the data range is 10^4，Generalized backpack做法需要记录of维度大于一维，Not be considered。
It's easy to think of「Two points」，Obviously the maximum selection quantity ans 为分割点of数组上具有「Secondary」：
1. The quantity is less than equal to ans ofcourse能够构造出合法排序（Consider making subtraction on the longest legal sequence）；
2. Use the quantity greater than ans ofcourse无法构造出合法排列。
此时Two points范围为 `[0,n]`，The problem converts to：
How to `O(n)` Check whether it can construct a length len of合法排列（accomplish `check` method）。
常规of线性扫描做法无法确定是否存在某个长度of合法排列，因此Two pointsNot be considered。
We need to use「greedy」思维考虑可能of方案。

Code：

import heapq
class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])

        # This will be a max-heap based on course duration
        q = []
        sum = 0
        for c in courses:
            d, e = c
            sum += d
            heapq.heappush(q, -d)
            if sum > e:
                sum += heapq.heappop(q)
        return len(q)