LeetCode : 630. Course Schedule III

 

문제)

 

1번부터 n번까지 번호가 매겨진 n개의 서로 다른 온라인 강좌를 수강할 수 있다.

각 강좌에 대해 courses라는 배열이 주어진다.

courses[i] = [durationi, lastDayi]는

i번째 강좌가 durationi일 동안 연속적으로 진행되어야 하며,

lastDayi일 이내에 끝나야 한다는 것을 의미한다.

당신은 1일부터 강좌를 시작할 수 있으며, 동시에 두 개 이상의 강좌를 수강할 수는 없다.
최대한 많은 강좌를 수강할 수 있도록 하려면 몇 개의 강좌를 들을 수 있는지 반환하면 되는 문제이다.

요약:
각 강좌는 연속된 durationi일 동안 진행되어야 하며, lastDayi일 이내에 완료되어야 한다.
강좌는 1일부터 시작할 수 있다.
동시에 두 개 이상의 강좌를 수강할 수 없다.
수강할 수 있는 최대 강좌 수를 반환.

 

문제 난이도 : 상

 

소요시간 및 풀이)

그리디 알고리즘을 사용해서 풀었다.

문제 난이도 치고는 생각보다 풀만했다.

 

강의를 종료 날짜(lastDay) 기준으로 정렬.

각 강의를 순회하면서, 현재 강의를 수강할 수 있는지 검사.
수강할 수 있다면, 현재 날짜를 갱신하고 힙에 추가.
수강할 수 없다면, 힙에서 가장 긴 강의를 제거하고 현재 강의를 추가할 수 있는지 검사

이를 통해 최적의 결과를 유지.

 

소요 시간 : 37분

 

정답 코드

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> maxHeap;
        int currentDay = 0;

        for (auto course : courses)
        {
            int duration = course[0];
            int lastDay = course[1];

            if (currentDay + duration <= lastDay)
            {
                // 현재 강의를 수강할 수 있다면 힙에 추가
                maxHeap.push(duration);
                currentDay += duration;
            }
            else if (!maxHeap.empty() && maxHeap.top() > duration)
            {
                // 현재 강의를 수강할 수 없지만, 힙에서 가장 긴 강의를 빼고 현재 강의를 추가할 수 있다면
                currentDay += duration - maxHeap.top();
                maxHeap.pop();
                maxHeap.push(duration);
            }
        }

        return maxHeap.size(); 
};