😢 백준 1931 : 회의실 배정

1931: 회의실 배정

Greedy 문제이다.
이번 문제는 어려워서 안 풀다가 한 번 건들봤다.

📌 Try 1

N = int(input())
time, nums = list(), list()
for _ in range(N):
  time.append(list(map(int, input().split())))

time.sort(key=lambda x:x[0])
  
for i in range(N):
    cnt, stack = 1, [time[i]]
  
    for j in range(i+1,N):
        if stack[-1][1] <= time[j][0]:
            stack.append(time[j])
            cnt += 1
    nums.append(cnt)

print(max(nums))

어떻게 접근해야 할지 몰라서, 단순하게 for문으로 풀었다.
하지만,, 시간초과 떴다.
코드도 난잡하다.

📌 Try 2

N = int(input())
inputArr = list()
for _ in range(N):
  inputArr.append(list(map(int, input().split())))

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

end, cnt = 0, 0
for x in inputArr:
  if x[0] > end:
    end = x[1]
    cnt += 1
    
print(cnt)

도저히 몰라서 다른 분 블로그를 참고했다.

빨리 끝나는 회의 순서대로 정렬을 해야 한다.
이유는 간단하다. 빨리 끝날수록 뒤에서 고려해볼 회의가 많기 때문이다.

이것이 알고리즘의 핵심이고, 직관적으로 이해해야 한다고 한다.

나는 직관적으로 이해가 되지 않아, 반례를 찾는 방식으로 이해했다.

조건 : 회의의 시작시간과 끝나는 시간이 같을 수도 있다.

inputArr.sort(key=lambda x:(x[1], x[0]))를 한 이유는 inputArr를 회의 종료 시간으로 한 번 정렬하고 회의 시작 시간으로 다시 한 번 정렬해야 하기 때문이다.

🎁 Reference

• [백준알고리즘] 1931번: 회의실배정 -Python
  https://suri78.tistory.com/26