BOJ 1931 회의실 배정

문제

접근 방법

제일 일찍 끝나는 회의실을 계속 넣으면 해결할 수 있으므로 그리디 알고리즘이라는 것을 알 수 있다.

틀린 접근

회의실이 끝나는 시간이 빠르다면 시작하는 시간도 빠를테니 끝나는 시간으로 정렬을 하여 푼다. 처음에 이렇게 생각을 했는데 생각해보면 끝나는 시간이 같은 회의도 있기 때문에 시작 시간에 대해서도 정렬을 해야 한다. 안 그러면 (1,2), (4,4), (3,4) 으로 정렬이 되었을 때 (3,4)를 하지 못하게 되는 예외 상황이 발생함

맞는 접근

회의실이 끝나는 시간에 대해서 정렬을 한 후에 시작하는 시간에 대해서도 정렬을 하여 끝나는 시간이 같은 회의가 생길 경우, 시작 시간이 빠른 것이 우선이 되도록 하여 푼다.

정답 코드

import sys
input = sys.stdin.readline

"""
끝나는 시간이 빠를수록 시작 시간도 빠르고 더 많은 회의를 넣을 수 있음.

끝나는 시간으로 sort한 다음에 순회
이전 회의의 끝나는 시간보다 현재 index 회의의 시작 시간이 빠르다면 skip
"""

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

# 끝나는 시간으로 정렬하되 같다면 시작하는 시간에 대해서 정렬
times.sort(key = lambda x: (x[1], x[0]))
tmp=times[0]
num = 1
for i in range(1,n):
  cur = times[i]
  if tmp[1] <= cur[0]:
    num+=1
    tmp = cur

print(num)


"""
끝나는 시간이 빠르기만 하다면 시작하는 시간도 빠르니까 끝나는 시간으로만 정렬하면 될 줄 알았는데 끝나는 시간이 같은 케이스를 생각하지 못했다.
"""