탐욕 알고리즘 - 회의실 배정문제 해법 -

1. 문제 유형

 

1-1) 예시

 

윤대리는 소프트웨어 개발팀들의 회의실 사용 신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다.

 

회의는 시작 시간과 종료 시간이 있고 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다.

 

가능한 많은 회의가 열리기 위해 회의실은 어떻게 배정해야할까?

 

 

1-2) 정형화

 

시작시간과 종료시간 $(s_{i}, f_{i})$가 있는 n개의 활동들의 집합 $A = \left\{ A_{1}, A_{2},... , A_{n} \right\}$이고 i는 1이상 n이하이다.

 

여기서 서로 겹치지 않는 최대 개수의 활동들의 집합 S를 구하는 문제

 

 

2. 문제 해법

 

모든 경우의 수를 조사할 수도 있지만 탐욕 알고리즘이 가능한 대표적인 문제이다.

 

2-1) 예시를 통한 설명

 

핵심 해법은 종료시간이 가장 빠른 순서대로 활동 집합을 먼저 정렬하는 것이다.

 

위와 같이 10개의 활동을 종료시간이 가장 빠른 순서대로 정렬해놓고, 가장 빨리 종료하는 $a_{1}$을 선택하면..

 

다음에 선택해야할 활동은??

 

겹치지 않아야하므로 $a_{2}$와 $a_{3}$는 선택 불가능하다

 

그래서 다음에 선택할 활동은 이전에 선택한 활동의 종료시간 이상의 시작시간을 가지면서 가장 빨리 종료하는 $a_{4}$이다.

 

 

그래서 위 과정을 계속 반복하면  $S= \left\{ a_{1}, a_{4}, a_{8}, a_{10} \right\}$으로 최대 개수의 겹치지 않는 활동 집합을 얻을 수 있다

 

 

2-2) 알고리즘

 

1) 종료시간이 빠른순서대로 정렬한다. 만약 종료시간이 서로 같다면 시작 시간이 빠른 순서대로 정렬한다.

 

2) 가장 빠른 종료시간을 가지는 활동을 선택한다.

 

3) 선택한 활동의 종료시간 이상으로 시작시간을 가지는(서로 겹치지 않도록) 다음 활동을 선택한다

 

4) 위 과정을 반복하여 모든 활동을 선택하면 최대 개수의 겹치지 않는 활동 집합을 얻는다

 

 

3. 연습문제1

 

SW Expert Academy

SW Expert Academy

 

Learn - course - programming advanced - sw 문제해결 응용3 탐욕 알고리즘

 

5202. sw 문제해결 구현 3일차 - 화물도크

 

24시간 운영되는 물류센터에 화물을 싣고 내리는 도크가 설치되어 있는데, 0시부터 다음날 0시 이전까지 도크의 사용 신청을 확인해서 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하고 싶다.

 

최대 몇대의 화물차가 이용할 수 있는지 알아내는 프로그램을 만드시오.

 

앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다. 예를 들어 앞 작업이 5시에 끝나면, 다음 작업도 5시에 시작 가능하다.

 

 

4. 풀이1

 

입력을 받고, 종료시간이 빠른 순서대로, 종료시간이 같다면 시작 시간이 빠른 순서대로 정렬한다

 

다음, 0시부터 시작을 하기 때문에 최초 종료시간을 b_e=0으로 초기화하고

 

정렬된 집합을 순회하여, 이전 작업의 종료시간 b_e <= 다음 작업의 시작시간 s이면 선택하고

 

다음 작업의 종료시간으로 b_e를 변경시킨다

 

T = int(input())

for t in range(1,T+1):
    
    n = int(input())

    time = []

    for _ in range(n):
        
        s,e = map(int,input().split())

        time.append((s,e))
    
    ##종료시간(time[1])이 빠른 순서대로, 종료시간이 같다면 시작시간(time[0])이 빠른 순서대로 정렬
    time_sort = sorted(time,key = lambda item:[item[1],item[0]])

    b_e = 0

    ans = 0

    for s,e in time_sort:
        
        if s >= b_e: #이전 작업의 종료시간(b_e) 이상의 다음 작업의 시작시간(s)이면.. 선택
            
            ans += 1
            b_e = e #이전 작업의 종료시간을 다음 작업의 종료시간으로 변경
    
    print('#'+str(t),ans)

 

 

5. 연습문제2

 

1931번: 회의실 배정 (acmicpc.net)

1931번: 회의실 배정

 

시작시간, 종료시간이 주어지는 회의실에 대하여 겹치지 않게 하면서 회의실을 사용하는 최대 개수를 구하는 문제

 

시작시간과 종료시간이 서로 같을 수 있다

 

 

6. 풀이2

 

그냥 완전히 위의 문제와 동일하다

 

아무튼 종료시간이 빠른 순서대로, 종료시간이 같다면 시작시간이 빠른 순서대로 정렬하는 것이 핵심이다

 

그 후 겹치지 않도록 선택하면 된다

 

시작시간과 종료시간이 서로 같다는 조건때문에 종료시간이 서로 같다면 시작시간이 빠른 순서대로 정렬해야한다

 

예를 들어

 

3
1 3
8 8
4 8

 

위와 같은 경우에.. 종료시간이 빠른 순서대로만 정렬해버리면

 

1 38 84 8이 되어서 2개밖에 선택 못할 수가 있다

 

하지만 실제로는 1 3, 4 8, 8 8을 선택하면 3개를 선택할 수 있다

 

 

from sys import stdin

n = int(stdin.readline())

room_list = []

for _ in range(n):
    
    s,e = map(int,stdin.readline().split())

    room_list.append((s,e))

#종료시간이 빠른 순서대로, 종료시간이 같다면 시작시간이 빠른 순서대로 정렬
sorted_room_list = sorted(room_list,key=lambda item: [item[1],item[0]])

a = sorted_room_list[0][1]

cnt = 1

#이전 작업의 종료시간 이상으로 다음 작업의 시작시간이 시작하면, 그것을 선택
#다음 작업의 종료시간으로 a를 변경
for s,e in sorted_room_list[1:]:
    
    if s >= a:
        
        cnt += 1
    
        a = e

print(cnt)