[BOJ] 1931번: 회의실 배정 (Greedy)

 

 

문제 링크

https://www.acmicpc.net/problem/1931

 

 

TIL

• 처음에는 key-value의 형태로 시간을 기록할까 했지만, 시간 범위가 2^31인걸보고 절대 안되겠다 싶어서 다른 방법 생각
• 남은 방법은 주어진 회의들에 대해서 순회하면서 넣을까 말까 고민하는 것이었기에 빠른 회의 순으로 나열해야한다고 생각함
• 나열한 미팅 리스트를 순회하며
  • 만약 다음 회의의 시작 시간이 현재 회의가 끝나는 시간보다 뒤면 가능 (cnt 추가하고 변수 업뎃)
    • if me <= meetings[i][0]:
    • 중요한 거는 여기서 =을 꼭 붙여야한다는 점 !!!! 이거 안해서 처음에 틀림. 끝나는 것과 시작하는 것은 동일할 수 있음
  • 만약 다음 회의의 끝나는 시간이 현재 회의 끝나는 시간보다 작으면 변수만 업뎃 (더 짧으니까)
  • 두 개 모두 포함되지 않는 경우에는 아무것도 실행안함
• 나름 빠르게 풀이가 생각나서 빨리 푼 문제지만 ,, 
  (그리디라는 걸 알고 풀어서 풀이가 바로 생각난걸수도 ...  ㅠ)

 

Code

[ 내 코드]

N = int(input())
meetings = []
for i in range(N):
    s, e = map(int, input().split())
    meetings.append((s,e))

meetings.sort()
cnt = 1
me = meetings[0][1]

for i in range(1, N):
    if me > meetings[i][1]:
        me = meetings[i][1]
        continue
    if me <= meetings[i][0]:
        cnt += 1
        me = meetings[i][1]
        continue
    else: continue

print(cnt)

 

 

 

[ 다른 사람 코드 궁금해서 찾아봄 ]

import sys

n = int(input())

endpoint: int = 0
answer: int = 0

arr = []

for i in range(0,n):
    a, b = map(int,sys.stdin.readline().rstrip().split())
    arr.append([a,b])

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

for newstart, newend in arr:
    if endpoint <= newstart:
        answer += 1
        endpoint = newend
print(answer)

 

• 나와 다르게 끝나는 시간이 더 짧은 경우, 업데이트를 안했음
• 이래도 되나? 싶어 고민해보니 어차피 Sort 하면 시작 시간이 같다는 전제 하에 끝나는 시간이 더 짧은 시간이 존재할 수 없지만, 
  • 시간 시간이 다른 경우에는 가능해서 .. 이 코드로는 반례가 발생하지 않을까 생각이 듦 (정답 코드이긴 했음 ,, )
  • (1, 8), (2,3), (3, 6) 인 경우에 안되지 않나 .. ? 라고 생각함
• ㅁ ㅣ 친 . 애초에 정렬은 끝나는 시간 기준으로 해서 그런 상황이 발생하지 않음!!!
  • 좋은 코드다 ~