[BOJ/Python] 1931번 문제풀이

문제 설명

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

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

풀이 과정

해당 문제는 그리디 알고리즘을 사용한 문제로, 풀이 과정은 다음과 같다.

 

문제 속 기준에 따라 회의실의 개수는 하나이고 회의가 시작하면 중간에 중단될 수 없으므로 빠르게 끝나는 회의 일수록 더 많은 회의가 진행될 수 있도록 끝나는 시간이 빠른 순서대로 정렬해야 한다.

 

또 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있는데 시작 시간이 끝나는 시간과 최대한 가까운 순서대로 있어야 회의 사이 시간을 최소한으로 줄여서 최대한 많은 회의가 진행될 수 있으므로 두번째 정렬 기준은 시작하는 시간이 빠른 순서이다.

 

해당 조건을 바탕으로 sorted 또는 sort 속의 정렬 옵션을 사용하여 정렬해보면 아래와 같다.

 

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]))

time = 0
answer = 0
for meeting in meetings:
    if time <= meeting[0]:
        time = meeting[1]
        answer += 1

print(answer)