[백준] #1931 회의실 배정(python)

📌문제

한 개의 회의실이 있는데 이를 사용하고자 하는 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

백준 1931번 문제

💡Idea

사실 이 문제는 인턴 코딩 테스트에서 풀었던 문제입니다. 다시 한 번 정리해보고 싶어서 풀어보았습니다🙋‍♀️

매 순간 최선의 선택을 하는 그리디 알고리즘으로 풀 수 있는 문제입니다.

종료 시간이 빠른 회의를 선택하면 다른 회의들로 채울 수 있는 시간이 더 늘어나게 됩니다. 그리고 종료 시간이 같다면 시작 시간이 이른 회의를 우선적으로 선택하는 것이 좋습니다.

시작 시간을 고려하는 이유는 아래와 같은 예시 때문입니다.

1 4
7 7
5 7

위와 같은 상태에서 종료 시간만 고려한다면 1 4와 7 7을 선택하여 최대 2개의 회의만을 진행할 수 있습니다.
하지만, 사실은 1 4 -> 5 7 -> 7 7의 순서로 3개의 회의를 모두 진행할 수 있습니다.
따라서, 종료 시간이 같다면 시작 시간이 이른 회의를 선택해야 더 많은 회의를 진행할 수 있습니다.

따라서, 종료 시간을 기준으로 오름차순 정렬, 시작 시간을 기준으로 오름차순 정렬을 하면 가장 많은 회의들을 선택할 수 있습니다.

💻코드

• ⏰ 시간 : 312 ms / 메모리 : 57760 KB

import sys
input = sys.stdin.readline

ans = time = 0 
meeting = [list(map(int, input().split())) for _ in range(int(input()))] 
meeting.sort(key=lambda x: (x[1], x[0])) # 회의 종료 시간 -> 시작 시간 순으로 정렬

for m in meeting:
    if m[0] >= time: # 1
        time = m[1]
        ans += 1

print(ans)

변수

• time : 현재 회의실에서 진행되고 있는 회의가 끝나는 시간을 담는 변수
• meeting : [회의 시작 시간, 회의 종료 시간] 로 회의의 정보를 저장하는 리스트

#1 : meeting의 회의들을 하나씩 확인하면서 만약 현재 회의실에서 진행되고 있는 회의의 종료 시간이 해당 회의의 시작 시간보다 이르다면, 해당 회의를 회의실에 배정할 수 있습니다.
회의를 배정하고, time을 배정한 회의의 종료 시간으로 변경합니다.
모든 회의를 확인할 때까지 반복합니다.