[백준] 회의실 배정 - 1931 Python 파이썬 풀이

 

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

1931번: 회의실 배정

그리디 알고리즘 문제입니다. 😀
한 유튜버분이 그리디, 탐색, 동적 프로그래밍

각 50문제씩 풀어보는 것을 추천해 주셔서
그리디만 엄청 풀고 있습니다.😪

 

---

📝 접근 방식 & 문제 풀이

 

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

⦁ 접근 및 풀이

✔ 그리디 알고리즘의 핵심은 정렬이라고 했습니다.

   따라서 회의 시작 시간을 기준으로 먼저 정렬하고, 회의가 끝나는 시간을 기준으로 또 한 번 정렬한 후 문제를 풀면 됩니다. 간단해요!

 

---

📝 소스코드

 

⦁ 파이썬

N = int(input())
I = []
result = []

#N만큼 입력받기
for i in range(N):
    temp = list(map(int, input().split()))
    I.append(temp)

#그리디의 핵심은 정렬!
#회의 시작시간 정렬 후 회의 끝 시간 정렬 
I.sort(key = lambda x: x[0])
I.sort(key = lambda x: x[1])

#시작지점은 맨 처음 요소
cnt = 1
curr = I[0][1]

for j in range(1, len(I)):
    #시작시간이 현재 회의의 끝나는 시간 이상이라면 cnt++, curr 교체 
    if I[j][0]  >= curr:
        cnt += 1
        curr = I[j][1]
        continue

print(cnt)

 

 

---

 

---