[백준 1931번] 회의실 배정

# 회의실 배정

n = int(input())
list = []

count = 0
last_time = 0

for i in range(n):
    start, end = map(int,input().split())
    list.append((start,end))

# 시작시간 기준으로 오름차순 정렬
list.sort(key=lambda x:x[0])

# 종료시간 기준으로 오름차순 정렬
list.sort(key=lambda x:x[1])

# 회의 시간이 겹치지 않도록 회의 선정
for i in list:
    if i[0] >= last_time:
        count += 1
        last_time = i[1]

print(count)

이번 문제는 본인이 문제를 잘못 읽게 되어 많이 헤맸던 문제였다.

 

여태까지 그리디 문제를 풀 때 주어진 값을 이용해서 최소/최대한의 선택지를 찾는 문제를 많이 접해서 그런지 입력으로 받은 n값을 주어진 시간이라고 착각하고 방황을 했었다 .. 🥲

 

각설하고, 이번 문제의 목표는 시작시간과 종료시간이 주어진 회의들을 겹치지 않게 하되 최대한 많은 회의를 할 수 있도록 만드는 것이다.

여기서 핵심적인 아이디어는 최대한 많은 회의를 하기 위해서는 종료시간이 빠른 순서대로 회의를 진행하는 것이다 ! (Greedy 알고리즘)

 

그리고 놓쳐서는 안되는 점은 (10,10)과 (9,10)과 같이 종료시간이 같지만 시작시간이 같은 경우에는 시작시간이 빠른 순서대로 먼저 진행해야 최대한 많은 회의를 할 수 있다.

 

따라서 먼저 시작시간을 기준으로 오름차순 정렬을 한 뒤, 종료시간을 기준으로 또 한번 오름차순 정렬을 해주어야 한다.

 

마지막으로 정렬된 회의를 차례대로 진행하면서 회의시간이 겹치지 않게끔 회의를 선택하면 된다 :)

 

(다음부터는 문제를 유심히 읽고 푸는 연습을 하자 ,,)