백준 1931 - 회의실 배정

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

1931번: 회의실 배정

 

 

 

 

 

 

이 문제는 시작 시간과 끝나는 시간으로 주어지는 여러 개의 회의 정보를 입력받아, 각 회의가 겹치지 않고 사용될 수 있는 회의실의 최대 개수를 구하는 문제이다. 그리디 알고리즘을 활용하는 대표적인 문제이다.

 

 

1. 끝나는 시간을 기준으로 오름차순 정렬

회의를 최대한 많이 하기 위해서는, 시작 시간이 중요할까? 끝나는 시간이 중요할까?

1시에 시작해서 5시에 끝나는 회의와 1시에 시작해서 9시에 끝나는 회의를 입력받았다고 가정해보자.

1시에 시작해서 5시에 끝난다면, 5시가 넘어서(5시도 포함) 진행되는 회의 전체가 진행 가능 회의 후보에 포함될 수 있기 때문에, 1시에 시작해서 9시에 끝나는 회의보다 더 폭넓은 선택지를 가지게 된다. 물론, 9시에 끝나는 경우도 최대 개수 회의 경우에 포함될 수 있다. 하지만, 9시에 끝나는 회의가 갖는 선택지는 5시에 끝나는 회의가 갖는 선택지에 포함되기 때문에 해당 회의를 선택하는 것이 의미가 없다. 

따라서, 끝나는 시간을 기준으로 오름차순 정렬이 필요하다.

 

 

2. 끝나는 시간이 같은 경우엔 시작 시간을 기준으로 오름차순 정렬

시작 시간과 끝나는 시간이 동일한 회의도 존재한다고 했다.

만약, 1시에 시작해서 2시에 끝나는 회의와 2시에 시작해서 2시에 끝나는 회의를 입력받았다고 가정해보자.

최대 횟수를 가지기 위해서는, (2, 2)만 선택하는 것이 아니라, (1, 2)와 (2, 2)를 모두 선택하여 총 2번의 회의를 진행하는 것이 최대 회의 개수가 된다.  그렇기 때문에, 끝나는 시간을 오름차순 정렬 후, 시작 시간도 오름차순 정렬이 필요하다.

 

 

정리해보자면,

회의가 끝나는 시간을 기준으로 오름차순 정렬한 뒤, 시작 시간을 기준으로 오름차순 정렬을 하여 회의를 줄 세운 다음, 진행 가능한 회의의 개수를 세면 된다. 진행 가능한 회의의 조건은, 이전 회의가 끝난 시간이 해당 회의의 시작 시간보다 작다는 것이다. 그래야 진행 가능-

 

 

풀이코드)

import sys
N = int(input())
con = []
for i in range(N):
    con.append(list(map(int, sys.stdin.readline().split())))

con.sort(key=lambda x:(x[1], x[0])) # 회의가 끝나는 시간을 기준으로 오름차순 정렬하되, 시간이 같은 경우엔 시작 시간을 기준으로 오름차순 정렬

cnt = 0
time = 0

# 시작 시간이 이전 회의의 끝나는 시간보다 작거나 같은 경우에 카운트 
for c in con:
    if c[0] >= time:
        cnt += 1
        time = c[1]

print(cnt)