[백준 1931] 회의실 배정(Feat.Python)

문제

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

풀이

• 본인은 이 문제를 보자마자 그리디 알고리즘을 떠올렸다.
• 하지만 본인이 고민했던 것에는 2개가 있다.
  • 시작 시점이 빠른 것으로 정렬을 하고 이를 기점으로 끝나는 시간을 비교해서 가능한 회의의 갯수를 세어야 할까?
  • 끝나는 시점이 빠른 것으로 정렬을 하고 이를 기점으로 끝나는 시간을 비교해서 가능한 회의의 갯수를 세어야 할까?
• 결론은 끝나는 시간이었다. => 시작 시점이 빠른 것으로 정렬을 했을 때, 시작하는 시간이 가장 빠르고 가장 늦게 끝날 경우 1개의 회의만 가능하게 됨으로 우리가 원하는 구상, 원하는 동작을 하지 않는다.
• 따라서 끝나는 시점을 기점으로 최대한 많은 회의를 넣어주어야 한다.

import sys
input = sys.stdin.readline
N = int(input())
refer = [list(map(int, input().split())) for _ in range(N)]
refer.sort(key=lambda x : [x[1], x[0]])
ans = [refer[0]]
for i in range(N-1):
    if ans[-1][1] <= refer[i+1][0]:
        ans.append(refer[i+1])

print(len(ans))

 

• refer라는 배열에는 각 회의의 시작 시각, 끝나는 시각이 담여있다. ( [[1,2],[3,4],[5,6],....) 이런 형태이다.
• 이렇게 입력받은 refer라는 배열을 sort() 함수와 lambda 식을 사용하여 끝나는 시간 (코드에서는 x[1])을 기점으로 정렬 하고자 한다.
• ans에 가장 처음에 있는 회의, 즉 무조건 시작하는 회의를 하나 넣어주고, 그다음 for문을 통해 refer에 있는 회의들을 하나씩 순회하면서 if문(끝나는 시각이 다음회의의 시작하는 시각보다 빨리 끝나는지) 확인하고 그렇다면 ans 배열에 추가
• if문에서는 ans에 들어있는 가장 마지막 원소의 끝나는 시점을 보고자 한다.
• 그리고 ans배열의 원소의 갯수가 가능한 모든 회의의 갯수가 될 것이다.