[BOJ] 1931번: 회의실 배정

✏️ 문제

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

 

🤖 입출력 예시

 

💡 풀이

예전에 풀었던 문제인데 백준 1374번: 강의실, 11000번: 회의실 배정과 거의 똑같은 로직으로 풀이 가능한 그리디 유형이다.

 

코드를 다시 보니까 어제 정리한 강의실 문제와의 차이점은 정렬 기준이었다. 시작 시간 기준으로 정렬할 때와 종료 시간 기준으로 정렬할 때 어떤 부분에서 차이가 있는 거지?

 

👩‍💻 코드

import sys

input = sys.stdin.readline

N = int(input())

meetings = []

for _ in range(N):
    start, end = map(int, input().split())
    
    meetings.append([start, end])

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

first_meeting = meetings[0]

meeting_end = first_meeting[1]

answer = 1

for i in range(1, len(meetings)):
    if meetings[i][0] >= meeting_end:
        answer += 1
    
        meeting_end = meetings[i][1]

print(answer)