[Python] 백준 #1931- 회의실 배정[try_again]

문제

---

1931번: 회의실 배정

코드

---

 

Another answer

import sys 
input=sys.stdin.readline

N = int(input()) 
cnt=1

time = [[0]*2 for _ in range(N)] 
for i in range(N): 
    start, end = map(int, sys.stdin.readline().split()) 
    time[i][0] = start 
    time[i][1] = end 
time.sort(key = lambda x: (x[1], x[0])) 

end_time = time[0][1] 
for i in range(1, N): 
    if time[i][0] >= end_time: 
        cnt += 1 
        end_time = time[i][1] 
print(cnt)

풀이

---

이 문제는 그리디 문제다. 우선 그리디 문제라는 걸 파악할 수 있는 이유는 빨리 끝나는 것들을 고르면 그리디스럽게 제일 많은 회의 수를 구할 수 있다. 따라서 가장 많은 회의의 수를 알기 위해서는 빨리 끝나는 회의 순서대로 정렬을 해야 한다. 이유는 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다. 따라서 우선 끝나는시간을 기준으로 오름차순으로 정렬하고 문제 조건중에 같은시간에 회의가 시작하고 끝날 수도 있다라는 말이 있는게 보이는가?? 이것때문에 조건하나를 추가해줘야 하는데 예를들어 시작,끝 순으로 (3,3)과 (1,3)이 들어왔다고 하자. 정렬을 끝나는시간 기준으로만 한다면 끝나는시간이 같을 때는 입력순서 기준이므로 그대로 (3,3) (1,3)이 된다. 그런데 이때 (1,3)을 먼저 하면 (3,3)도 할 수 있지만 (3,3)을 먼저하면 (1,3)을 못하게 된다. 따라서 시작시간을 기준으로도 오름차순 정렬을 해줘야한다. 이 조건이 필요한 이유는 위에서도 말했듯이 같은시간에 회의가 시작되고 끝날 수도 있다는 조건이 있기 때문이다. 즉 회의시간들을 먼저 끝나는 시간 기준으로 정렬하고 이후에 시작시간 기준으로 정렬한뒤 아래 계산을 수행해주면 답이 나오게 된다. 아래 계산은 그냥 맨처음 회의를 무조건 한다고 시작하고, 다음회의는 이전 회의가 끝난 이후에 시작할 수 있으므로 전 회의의 끝나는 시간을 end_time에 갱신해주면서 다음회의의 시작시간이 end_time보다 큰 경우만 회의를 할 수 있으므로 cnt를 늘려주게 된다.