[Python] 회의실 배정(그리디)

문제

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

▣ 입력설명
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정
보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

▣ 출력설명
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

▣ 입력예제 1
5
1 4
2 3
3 5
4 6
5 7

▣ 출력예제 1
3

cf) 예제설명
(2, 3) , (3, 5), (5, 7)이 회의실을 이용할 수 있다.

 

---

풀이

n = int(input())
cnt = 0
time = []

for _ in range(n):
    s, e = map(int, input().split())
    time.append((s,e))
time.sort(key=lambda x:(x[1], x[0]))    # x[1]을 1순위, x[0] 을 2순위로 해서 정렬

last = 0 # 회의의 마지막 시간을 저장

for i,j in time:    # 시작시간, 끝나는 시간
    if i >= last:   # 회의를 할 회의의 시작시간이 현재 진행하고 있는 회의의 끝나는 시간보다 이후이면
        last = j    # 회의를 했으니 끝나는 시간 변경
        cnt += 1

print(cnt)

 

---

설명

그리디 알고리즘 관련해서도 정리가 잘 안됐어서 문제 접근이 불가능 했다.

 

- 그리디 알고리즘: 미래를 생각하지 않고 현재 차례에서 최고의 답을 찾는 문제. 보통은 정렬로 찾음

 

** lambda 함수 -  key 가 여러개 일 때 정렬 우선순위 정하기

- lambda 함수는 특정 요소를 기준으로 정렬의 기준을 정할 수 있다!

- x[1] 을 기준으로 정렬했다가 x[1]이 동일하다면 x[0]을 기준으로 정렬하는 식으로 우선순위를 정할 수 있음

time.sort(key=lambda x:(x[1], x[0]))    # x[1]을 1순위, x[0] 을 2순위로 해서 정렬

 

<알고리즘 설명>

가장 빨리 끝나는 회의를 찾아야 회의를 많이 할 수 있다!!

 

1. 종료 시간을 기준으로 오름차순 정렬

2. 제일 처음부터 진행 가능한 회의들을 진행

3. 해당 종료시간 전에 시작하는 회의는 무시