[Leetcode] 630. Course Schedule III

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

---

소요기간(연속), 완료되어야 하는 기간을 가진 course들의 배열 courses이 입력으로 주어진다.

1일차부터 시작하고 2개의 코스를 한 번에 들을 수는 없다.

수강할 수 있는 최대 코스 수를 구하라.

---

courses 배열을 완료되어야 하는 기간의 오름차순으로 정렬한다.

우선순위큐를 만든다. 이 큐에는 현재까지 수강가능한 최대 코스 수를 가지는 코스들의 수강기간(duration)로 이루어져 있다. (왜 duration을 넣는지는 뒤에서 설명할 예정(1))

큐에 있는 코스들을 모두 수강했을 때 쇼요기간을 day 변수에 저장해둔다.

 

정렬된 courses 배열을 앞에서부터 탐색하면서 큐에 넣을 수 있는지 판단한다.

i) 만일 탐색중인 코스를 수강할 수 있다면 (탐색중인 코스의 lastDay >= day + 탐색중인 코스의 duration)

   큐에 현재 코스의 수강기간을 넣고 day 변수를 갱신한다. (day + duration)

ii) 현재 코스를 수강할 수 없다면 큐의 가장 처음있는 값을 비교해서 교환 가능한지 확인해야 한다.

    문제에서 구하고자 하는 값은 코스의 수다. 따라서 현재 탐색하는 코스를 추가하기 위해 두 개 이상의 코스를 제거하는건 손해다.

    그렇다면 현재 수강중인 코스들 중 어느 코스와 탐색 중인 코스를 바꿀때 이득인지 생각해봐야한다.

    앞으로 추가되어야 할 코스들을 하나라도 더 많이 넣기 위해서는 총 수강시간이 적을수록 이득이다. 

    만료시간은 확인하지 않아도 되는가를 생각해봤을 때 큐에 들어갔다는 이야기부터가 만료기간 내에 수강가능하다는 의미가 되므로 큐에 넣은 후 부터는 코스의 수강기간을 확인할 필요가 없다.

    즉, 현재 수강중인 코스들 중 가장 긴 수강시간을 가지는 코스(1)대신 탐색 중인 코스를 수강했을 때 lastDay 내에 수강이 가능하며, 총 수강시간이 감소한 경우 탐색 중인 코스를 대신 수강하게 한다.

 

탐색이 끝났을 때 큐에 있는 코스들의 수가 정답이 된다.

 

시간복잡도는 O(NlogN)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/630.%20Course%20Schedule%20III.cpp