[시작 시간, 종료 시간] 형태의 구간(interval) 리스트가 주어졌을 때, 각 구간은 하나의 강의(코스)의 시작 시간과 종료 시간을 나타냅니다. 이때 동시에 한 과목만 수강할 수 있고, 다음 강의의 시작 시간은 반드시 이전 강의의 종료 시간보다 늦어야 한다는 조건에서, 수강할 수 있는 최대 강의 수를 구하는 문제입니다.
예를 들어 입력이 times = [[3, 6], [6, 9], [7, 8], [9, 11]]이라면, [3, 6], [7, 8], [9, 11] 세 개의 강의를 차례로 수강할 수 있으므로 결과값은 3이 됩니다.
해결 접근 방식: 그리디 알고리즘
이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "종료 시간이 가장 빠른 강의부터 선택하면, 다음 강의를 들을 수 있는 여유 시간이 최대한 많이 확보된다"는 것입니다.
- 강의 목록을 종료 시간 기준으로 오름차순 정렬합니다.
- 카운터(counter)는 0으로, 마지막 종료 시간(end)은 -1로 초기화합니다.
- 모든 강의를 순회하면서, 시작 시간이 현재 end보다 큰 경우 해당 강의를 선택합니다.
- 강의를 선택할 때마다 counter를 1 증가시키고, end를 해당 강의의 종료 시간으로 갱신합니다.
- 순회가 끝나면 counter 값을 반환합니다.
예제 코드
class Solution:
def solve(self, times):
times.sort(key=lambda x: x[1])
counter = 0
end = -1
for i in range(len(times)):
if times[i][0] > end:
counter += 1
end = times[i][1]
return counter
ob = Solution()
times = [
[3, 6],
[6, 9],
[7, 8],
[9, 11]
]
print(ob.solve(times))
입력
[[3, 6], [6, 9], [7, 8], [9, 11]]
출력
3
복잡도 분석
정렬 단계에서 O(n log n)의 시간이 소요되며, 이후 순회는 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 추가 자료구조 없이 상수 공간만 사용하므로 O(1)입니다. 이처럼 종료 시간 기준 정렬과 그리디 선택만으로도 최적해를 보장할 수 있습니다.