백준 1931 회의실 배정

회의실 배정

풀이 계획

• 감이 안잡힌다. 다른 사람 풀이에서 힌트 얻음.
• 끝나는 시간에 따라 정렬.
• 정렬된 리스트 순회하며, 시간표에서 가장 나중 회의의 끝나는 시간 이후에 시작하는 회의를 고름!

import sys
input = sys.stdin.readline
N = int(input())
meetings = []
for _ in range(N):
    meetings.append(list(map(int, input().split())))
meetings.sort(key=lambda x:(x[1], x[0]))

schedule = [meetings[0]]
for meeting in meetings[1:]:
    if meeting[0] >= schedule[-1][1]:
        schedule.append(meeting)

print(len(schedule))

• 2차원 배열에서 특정 인덱스를 기준으로 sort할 수 있다.
  • meetings.sort(key=lambda x:(x[1], x[0]))
  • 1번째 항을 기준으로 오름차순 정렬, 그 속에서 0번째 항을 기준으로 오름차순 정렬
  • -x[1] 식으로 -를 붙이면 내림차순 정렬이 된다.
  • 같은 시각에 끝나는 회의의 경우, 이전 회의가 끝나는 시각 이후에만 시작하면 같게 카운팅 된다. 그러나 이전 회의가 끝나는 시각에 시작과 끝을 같이 하는 회의를 카운팅해야 했다. 회의 끝이 빠른 순서대로 나열한 후, 회의 시작이 빠른 순서대로 나열해야 했다.
  • 반례
    2
    2 2
    1 2
    -> 2 출력