(Python) - BOJ(1931번) : 회의실 배정

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

1931번: 회의실 배정

---

• 해설 : 

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

 

 

 

---

• 풀이 :

그리디한 방법을 사용하면 해결할 수 있다.

종료시간이 빠른 회의실들 중 시작시간이 빠른 순서대로 가능한 한 많이 회의실을 대여하면 된다.

 

 

 

---

• 소스코드 : 

 

num_of_meeting = int(input())
x = []
for i in range(num_of_meeting):
    start , end = input().split()
    start = int(start)
    end = int (end)
    x.append([start,end])
 
count = 0
end_time = 0
x.sort(key=lambda x:x[0])
x.sort(key= lambda x:x[1])
for i in range(num_of_meeting):
    if int(x[i][0]) >= end_time:
        end_time = int(x[i][1])
        count +=1
print (count)