생각해봅시다!

• 최대한 많은 회의를 일정에 포함시키려면, 종료 시간이 제일 빠른 회의를 우선 선택해야 합니다.
  • 그래야 그 이후에 다른 회의를 할 시간이 더 확보되겠죠.
• 먼저 종료 시간이 제일 이른 회의를 진행합니다.
  • 회의가 끝나면, 시작 시간이 더 나중인 회의 중에서 종료 시간이 가장 이른 회의를 선택합니다.
  • 이 과정을 반복하여 문제를 해결합니다.
• 빨리 끝나는 회의를 선택하는 최선의 선택을 반복하므로, 탐욕법을 사용하는 문제로 볼 수 있습니다.

정렬이 핵심이다

import sys
input = sys.stdin.readline

N = int(input())
times = []

for _ in range(N):
    s, e = map(int, input().split())
    times.append((s, e))

• 우선 times 리스트에 각 회의의 시작, 종료시간을 (시작, 종료) 형태로 삽입합니다.

# 종료 -> 시작시간이 빠른 순 sort
times.sort(key=lambda x: (x[1], x[0]))

total = 1   # 가능한 회의 수
curr_finish = times[0][1]     # 현재 회의가 끝나는 시간

• times를 종료 시간이 이른 순으로 정렬합니다. 종료 시간이 이른 회의를 우선 선택하기 위해서입니다.
  • 종료 시간이 같다면, 시작 시간이 빠른 순으로 정렬합니다. (이유는 밑에 설명)
  • 파이썬 sort 메서드의 key 변수에 튜플을 반환하는 함수를 넘기면, 정렬은 튜플의 첫 요소를 기준으로, 같을 경우 둘째 요소를 기준으로 이루어집니다.
• 그러면 times[0]에는 종료시간이 제일 이른 회의가 저장되어 있겠죠. 일단 이 회의를 일정에 포함시킵니다.
  • 진행된 회의 수를 세는 변수 total을 1(현재 회의를 포함하므로)로 초기화하고,
  • 현재 회의의 종료시간을 curr_finish에 저장합니다.

for s, e in times[1:]:
    # 현재 회의가 끝남
    if s >= curr_finish:
        total += 1
        curr_finish = e

print(total) 

• 이후 times의 각 원소를 순회하며 나머지 회의도 확인합니다.
• 이때 현재 진행중인 회의가 끝난 후에 시작할 수 있는 회의만 선택합니다. (s >= curr_finish)
  • 새로운 회의를 일정에 포함시키면, total에 1을 더하고, 종료 시간을 새로운 회의의 종료시간으로 갱신합니다(curr_finish = e)

🤔 종료 시간이 같을 때, 굳이 시작 시간을 기준으로 정렬하는 이유가 있나요?

• 한 회의의 종료시간과 다른 회의의 시작시간이 같으면, 두 회의를 연달아 진행할 수 있습니다.
  • e.g., 회의 일정이 [(2, 5), (2, 2), (0, 2)]인 경우, (0, 2) -> (2, 2) -> (2, 5) 순으로 진행할 수 있습니다.
• 종료 시간 기준으로만 정렬하면 결과는 [(2, 2), (0, 2), (2, 5)]가 됩니다.
  • 이 경우 일단 첫 회의 (2, 2)를 선택하면, 둘째 회의 (0, 2)의 시작 시간이 첫 회의 2의 종료시간보다 빠르므로, (0, 2)가 정답에서 누락됩니다.
  • 조건문 if s (0) >= curr_finish (2)가 거짓이 되겠죠.
• 반면 제 풀이처럼 종료 시간 -> 시작 시간 기준으로 정렬하면
  • 정렬 결과는 [(0, 2), (2, 2), (2, 5)]가 됩니다.
  • 이 경우 세 회의를 모두 선택할 수 있습니다.

풀이

import sys
input = sys.stdin.readline

N = int(input())
times = []

for _ in range(N):
    s, e = map(int, input().split())
    times.append((s, e))

# 종료 -> 시작시간이 빠른 순 sort
times.sort(key=lambda x: (x[1], x[0]))

total = 1   # 가능한 회의 수
curr_finish = times[0][1]     # 현재 회의가 끝나는 시간

for s, e in times[1:]:
    # 현재 회의가 끝남
    if s >= curr_finish:
        total += 1
        curr_finish = e

print(total) 

시간 복잡도

• 회의가 $N$개일 때, 정렬 과정에서 $O(N \log N)$.
• 그리고 각 회의를 for문으로 확인하며 $O(N)$.
• 최종 $O(N \log N)$.

기억할 점

• 탐욕법엔 정렬이 많이 쓰인다. 매 순간 제일 작은/큰 값을 고르는 것도 탐욕적 선택이기 때문이다.