이 문제의 핵심은 "강의가 끝나는 시간이 이르면 이를수록 넣을 수 있는 강의의 수가 더 많다!" 라는 점이다.
즉 강의가 끝나는 시간을 기준으로 이 문제를 해결하면 비교적 쉽게 풀 수가 있다.
그럼 이를 위해서 우리가 알아야 할 코드는 "강의가 끝나는 시간 기준으로 나열"하는 코드이다. 이는 파이썬 내장함수 sorted 함수를 통해 구현이 가능하다.
# 내용물을 그 내용물 리스트의 2번째 요소의 크기를 토대로 분류한다.
a = sorted(내용물, key=lambda x: x[1])
그럼 입력값을 바로 이렇게 sorted 함수로 변환하는 코드를 작성한다고 치면,
import sys
N = int(input()) # 강의 수를 받는다.
courses = [] # 강의 수를 담을 리스트 준비.
# 강의들을 리스트에 담는다.
for i in range(N):
courses.append(list(map(int, sys.stdin.readline().split())))
# 리스트의 첫번째 요소를 기준으로 정렬한다.
sorted(courses, key=lambda x: x[1])
위처럼 표현할 수 있다.
그러고 나선 그렇게 정렬된 강의 리스트를 토대로 강의가 끝나는 시간과 다른 한 강의의 시작시간을 비교해서, 시작시간이 크거나 같을 경우에 변수를 하나하나 더하는 방식으로 진행을 한다.
코드
import sys
# 강의 수를 받는다.
N = int(input())
# 강의를 담을 리스트를 마련한다.
courses = []
# 강의 수 만큼 for 루프를 돌린다.
for i in range(N):
# 각각의 강의의 입력값을 courses 리스트에 담는다.
courses.append(list(map(int, sys.stdin.readline().split())))
# 강의 리스트를 두번째 요소(수업이 끝나는 시간)이 작은 순으로 정렬하고 이를 courses_sorted에 저장한다.
courses_sorted = sorted(courses, key=lambda x:x[1])
# 수업이 끝나는 시간을 담을 임시 변수 지정 - last_end
last_end = 0
# 최대 강의수를 기록할 변수 지정 - max_num_course
max_num_course = 0
# 강의 시작시간과 끝시간을 하나하나 빼온다.
for s,e in courses_sorted:
# 만약 시작 시간이 이전 강의의 끝나는 시간보다 크거나 같을 경우
if s>=last_end:
# 이전 강의의 끝나는 시간을 갱신해주고,
last_end = e
# 최대 강의 수에 하나를 더한다.
max_num_course += 1
print(max_num_course)
