[BOJ] 백준 1931번 회의실 배정

백준 1931번 회의실 배정 (실버1)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

문제 풀이

전형적인 그리디 알고리즘이다. 일단 가장 쉽게 생각하자.
최대한 많은 회의를 할 수 있게 하려면 어떻게 해야 할까?

1. 시작 순서에 따라 정렬한 후 구한다? (x)
   • 만약 (1,13) (2,5) (5,13) 이 있다면 (1,13)만 카운트하고 나머지는 카운트 안함.
   • (2,5) (5,13) 총 2개가 카운트 되어야함
2. 종료 순서에 따라 정렬한 후 구한다
   • 위 예시에서 종료 순서에 따라 정렬하면 (2,5) (5,13) (1,13) 이 됨.
   • 이 경우에는 2개가 카운트 된다.
   • 하지만 반례도 있다.
   • (1,3) (8,8) (4,8)과 같은 경우 종료시간으로만 정렬하면, 이와 같이 정렬될 수도 있다.
   • 그렇다면 (1,3) (8,8) 두 개만 카운트 되기 때문에 틀리게 된다.
   • 실제로는 1~3시 1번, 4~8시 2번, 8~8시 3번으로 총 3개가 나와야한다.
   • 그러므로 2번째 우선순위로 시작 시간으로도 정렬을 해준다.

N = int(input())

data = []
for i in range(N):
    a, b = map(int, input().split())
    data.append((a, b))
data.sort(key=lambda x: (x[1], x[0]))

result = []
result.append(data[0])

for i in range(1, len(data)):
    if data[i][0] >= result[-1][1]:
        result.append(data[i])
print(len(result))