알고리즘 - Python / 백준 - 1931번 : 회의실 배정

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

1931번: 회의실 배정

 

---

풀이

• 그리디 알고리즘로 풀어야 하는 문제인 것 같아 그리디 알고리즘에 사용될 수 있는 기준점이 뭐가 있나 살펴보았다.
• 회의 시간 , 회의 시작시간 , 회의 끝나는 시간 정도로 추려졌고 3가지 경우에 대해서 생각해본 결과 끝나는 시간으로 그리디 알고리즘을 진행하니 풀리는 문제였다.
• 회의가 끝나는 시간이 같은 경우들에서도 따로 정렬이 필요해 회의가 끝나는 시간으로 정렬하고 이후 회의가 시작하는 시간으로 한번더 정렬을 해 그리디 알고리즘을 진행하였다.

 

import sys

n = int(sys.stdin.readline())
stack = []
for _ in range(n):
  s ,f = map(int, sys.stdin.readline().split())
  stack.append([s,f,f-s]) # f-s는 총 회의시간 , 코드에서 사용하지 않음
stack.sort(key = lambda x : (x[1],x[0]))

ans = 0
fn_time = 0

for i in range(0,len(stack)):
  if stack[i][0] >= fn_time:
    fn_time = stack[i][1]
    ans += 1
print(ans)

---