[백준] 1931번 - 회의실 배정 - 그리디 알고리즘

문제

 

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

입력

 

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

 

출력

 

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

 

입력  예시

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

출력 예시

4

 

 

풀이

 

회의실을 배정하기 위해선 시작시간과 끝나는 시간을 파악하고

# 입력 받은 순서
[(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]

 

 

 

 

그리고 시작 시간 정렬을 통해 먼저 시작되는 회의들을 순서대로 배치합니다.

[(0, 6), (1, 4), (2, 13), (3, 5), (3, 8), (5, 7), (5, 9), (6, 10), (8, 11), (8, 12), (12, 14)]

앞 회의 끝나는 시간 <= 뒤 회의 시작시간의 조건에 해당해야 합니다.

 

그래야 회의 끝나고 다음회의가 세팅됩니다.

 

예를 들어, 첫 회의가 (0, 6) 라면 다음 회의는 6시 이후에 시작하는 회의가 세팅되어야 할 것입니다.

 

다음 회의는 그래서 (6, 10)이 됩니다. 이런 식으로 반복되면 첫 회의가 (0, 6) 일 때의 총 회의 개수를 구할 수 있습니다.

 

 

단, 여기서 주의해야 될 점이 있습니다!

 

뒤 회의 시작시간이 같은 회의들의 집합(예들 들어, 8 - 10, 8 - 12)들은 뒤 끝나는 시간으로 정렬을 해야합니다. 

 

왜냐하면 (8 - 12) (8 - 10) (10 - 12) (12 - 14)으로 정렬되어 있다면, (8-12)를 선택하는 것보다 (8 - 10) 회의를 선택하는 것이 회의를 더 배치할 수 있기 때문입니다.

 

그래서 먼저 시작시간 순으로 정렬한 상태에서 시작 시간이 같은 경우들은 끝나는 시간 순으로 정렬하는 과정을 거쳐야 합니다.

 

 

어떻게 정렬하면 좋을까?

 

sort()에서 lambda를 사용해서 정렬하면 쉽게 할 수 있습니다.

[python] Lambda 함수: 간결한 함수 정의와 활용

lambda를 활용한 정렬에 대해서 자세히 확인해보고 싶으시면 위 링크로 넘어가셔서 보시면 됩니다.

 

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

이렇게 사용할 수 있습니다.

 

 

최종 코드

import sys
input = sys.stdin.readline  # 표준 입력을 더 빠르게 받기 위해 sys.stdin.readline 사용

N = int(input())  # 첫 번째 입력으로 회의의 수 N을 받음
meetings = []  # 회의 시간을 저장할 리스트 초기화
count = 0  # 최대로 배정 가능한 회의의 수를 저장할 변수
end_time = 0  # 현재까지 배정된 회의 중 마지막 회의의 종료 시간

for _ in range(N):
    start, end = map(int, input().split())  # 회의의 시작 시간과 종료 시간을 입력 받음
    meetings.append((start, end))  # 회의 시간을 튜플 형태로 리스트에 추가

# 회의를 종료 시간이 빠른 순으로 정렬, 종료 시간이 같다면 시작 시간이 빠른 순으로 정렬
meetings.sort(key=lambda x: (x[1], x[0]))

# 모든 회의를 순회하면서
for meet in meetings:
    # 현재 회의의 시작 시간이 마지막으로 배정된 회의의 종료 시간보다 크거나 같으면
    if meet[0] >= end_time:
        count += 1  # 배정 가능한 회의 수를 1 증가
        end_time = meet[1]  # 마지막으로 배정된 회의의 종료 시간을 현재 회의의 종료 시간으로 업데이트

print(count)  # 최대로 배정 가능한 회의의 수 출력