[WEEK04] 26일차. 회의실 배정

백준 1931 회의실 배정

어느덧 WEEK04 2일차다.

회의실 배정 문제는 그리디 알고리즘으로 분류되는 문제로,
회의의 시작시간과 끝 시간이 주어지는데 최대한 많은 회의를 할 수 있는 경우의 수를 찾는 문제다.

끝나는 시간을 기준으로 정렬한 다음
처음 회의를 답에 넣고 현재 회의 끝 시간보다 다음회의 시작 시간이 크거나 같을 때 넣어주는 방식으로 해결했다.

85퍼센트 정도에서 틀렸습니다가 떴었는데 반례를 찾아보니
3
3 3
2 3
3 3

위 입력값이 주어졌을 때 답이 3이 나와야하는데 2가 나오는 문제가 있었다.

회의 시작 시간을 기준으로 먼저 정렬한 다음 회의 끝 시간을 기준으로 정렬하면 해결된다.

코드

import sys

inp = sys.stdin.readline

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

for i in range(N):
    times.append(list(map(int, input().split())))

times.sort(key=lambda x: x[0])
times.sort(key=lambda x: x[1])

ans = []

ans.append(times[0])

for i in range(1, N):
    if times[i][0] > times[i][1]:
        continue
    if ans[-1][1] <= times[i][0]:
        ans.append(times[i])

print(len(ans))