[백준 1931] [greedy] 회의실 배정 ❗

💻 백준 1931번 [회의실 배정]

1931번: 회의실 배정

풀이)

n = int(input())
lst = sorted([list(map(int,input().split())) for _ in range(n)], key = lambda x : (x[1],x[0]))
cnt = 1
cur = lst[0]
for i in range(1,len(lst)) :
    if lst[i][0] >= cur[1] :
        cnt+=1
        cur = lst[i]
print(cnt)

메모리	시간	언어	코드길이
57248KB	4308ms	Python 3	237B

 

과정)

빨리 끝나는 시간대로 회의를 정렬해야한다는 것은 알았다.

이외에 내가 놓쳤던 것은,

1. 회의가 끝나자마자 바로 다음 회의가 시작할 수 있다는 것

   (즉,  current 회의의 끝나는 시간 = next 회의의 시작 시간  이어도 가능하다는 것)

2. 시작시간과 끝나는 시간이 같을 수 있다는 것 (사실 이 조건은 내 코드에서 이미 해결이 된 조건이어서 문제를 맞추는데 지장은 없었음)

3. 정렬을 할 때, 끝나는 시간으로 정렬을 한 다음, 시작시간으로 한번 더 정렬해줘야 한다는 것

   나는 끝나는 시간으로만 정렬했어서 sorting시 key 함수로 lambda x : x[1]만 적어줬었음.

   그래서 추가로 시작시간인 x[0]도 추가하여 lambda x : (x[1], x[0])으로 바꿔줌

   이를 확인할 수 있었던 반례 ⬇⬇

# 틀린 코드
n = int(input())
lst = sorted([list(map(int,input().split())) for _ in range(n)], key = lambda x : x[1])
cnt = 1
cur = lst[0]
print(lst)
for i in range(1,len(lst)) :
    if lst[i][0] >= cur[1] :
        print(cur)
        cnt+=1
        cur = lst[i]
print(cur)
print(cnt)

# 입력
# 7
# 2 3
# 1 2
# 1 1
# 0 1
# 0 2
# 2 4
# 3 4
 
# 출력
# [[1, 1], [0, 1], [1, 2], [0, 2], [2, 3], [2, 4], [3, 4]]
# [1, 1]
# [1, 2]
# [2, 3]
# [3, 4]
# 4

# 정답 코드
n = int(input())
lst = sorted([list(map(int,input().split())) for _ in range(n)], key = lambda x : (x[1],x[0]))
cnt = 1
cur = lst[0]
print(lst)
for i in range(1,len(lst)) :
    if lst[i][0] >= cur[1] :
        print(cur)
        cnt+=1
        cur = lst[i]
print(cur)
print(cnt)

# 입력
# 7
# 2 3
# 1 2
# 1 1
# 0 1
# 0 2
# 2 4
# 3 4

# 출력
# [[0, 1], [1, 1], [0, 2], [1, 2], [2, 3], [2, 4], [3, 4]]
# [0, 1]
# [1, 1]
# [1, 2]
# [2, 3]
# [3, 4]
# 5

 

개인적으로 greedy 문제 중에서 핵심이라고 생각되고, 두고두고 봐두어야 할 문제라고 생각된다