[630] 630 | Course Schedule III | Python

---

문제 링크: https://leetcode.com/problems/course-schedule-iii/

---

문제

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [$duration_i$, $lastDay_i$] indicate that the ith course should be taken continuously for durationi days and must be finished before or on $lastDay_i$.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

---

조건

• 1 <= courses.length <= $10^4$
• 1 <= $duration_i$, $lastDay_i$ <= $10^4$

---

내 풀이

courses를 [duration, end]라 할 때, end가 작은 순으로 정렬시킨다..

기한이 얼마 없는 강의를 먼저 들어야하기 때문이다.

 

그 뒤, 정렬된 courses를 순서대로 훑는데, 현재까지 듣는데 걸린 시간(total) + duration이 end를 초과하지 않는다면, 이 강의는 들을 수 있으므로 ans에 추가한다.

그리고 훗날을 위해 ans를 정렬한다.

 

만약 total + duration이 end를 초과하고, max(ans)인 ans[-1]이 duration보다 크다면, 그 값을 빼고 현재 duration을 추가한다.

이렇게 해도 되는 이유는 max(ans)에 해당되는 duration과 end를 course1 [dur1, end1], 현재 값을 course2 [dur2, end2]라 하자.

dur1>dur2가 만족되며 end1 < end2이므로 course1을 듣지 않고 그 대신 course2를 듣는 개념이다.

 

이를 모두 마친 후에는 ans의 길이를 리턴하면 된다.

---

코드

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])
        total = 0
        ans = []
        
        for duration, end in courses:
            if total+duration <= end:
                total += duration
                ans.append(duration)
                ans.sort()
                
            elif ans and ans[-1] > duration: 
                total = total - ans[-1] + duration
                ans[-1] = duration
                ans.sort()
            
        return len(ans)