[백준 1931 🥈] 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

문제

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

 

입력

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

 

출력

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

 

문제 풀이

• 정렬과 그리디를 이용해서 푼 문제다.
• 우선 종료 시간을 기준으로 오름차순 정렬한다.
  • 왜냐하면 시작하는 시간이 빠르더라도 종료 시간이 늦다면 다른 회의를 시작할 수 없다.
  • 그러므로 더 많은 수의 회의를 배정하려면 종료시간이 빠른 순으로 회의를 배정해야 한다.
  • 단, 종료 시간이 같은 경우엔 시작 시간을 기준으로 정렬한다.
    • 왜냐하면 더 빠른 시작 시간을 먼저 배치해야 종료 시간이 같은 다음 회의를 배정할 수 있기 때문이다. 예를 든다면 다음과 같다.
      • (1,1), (2,3), (3,3)과 같은 회의 예정 시간이 있을 때 만약 같은 종료시간에 대한 시작시간순 정렬이 이루어져있지 않아서 (1,1), (3,3), (2,3)처럼 정렬되어 있다면 (1,1), (2,3), (3,3) 총 3개의 회의를 배정할 수 있음에도 불구하고 (1,1), (3,3)만을 선택하게 되기 때문이다.
• 현재 회의 종료 시간을 정렬된 회의 목록을 기준으로 첫 번째 회의의 종료 시간으로 초기화한다.
• 1번째 위치의 회의부터 탐색을 시작하면서 현재 회의 종료 시간(cur_endtime)과 탐색 중인 회의의 시작 시간을 비교했을 때 종료 시간이 작거나 같다면 해당 회의를 배치할 수 있기 때문에 현재 회의 종료 시간(cur_endtime)을 탐색 중인 회의의 종료 시간으로 갱신하고, 답의 개수 answer을 +1 해준다.

import sys

input=sys.stdin.readline

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

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

cur_endtime=meeting[0][1]
answer=1
for i in range(1,n):
    # 현재 회의의 종료 시간이 다음 회의 시작 시간보다 작거나 같다면 가능
    if cur_endtime<=meeting[i][0]:
        cur_endtime=meeting[i][1]
        answer+=1

print(answer)