[Python Algorithm] 그리디 알고리즘 - 회의실 배정

> 이분 탐색(결정알고리즘) & 그리디 알고리즘 (그리디알고리즘 편)
그리디 알고리즘 : 문제를 풀어나가는 과정, 단계에 있어서 가장 좋은 것을 찾는 ! 

그리디에서 어떻게 가장 좋은 것을 판별 ? -> 정렬 ! -> 차례로 선택

 

📖 문제 : 회의실 배정

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

 

 

 

입력설명
첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정 보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다.

 

출력설명
첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

입력예제 1
5
1 4
2 3

3 5

4 6

5 7

 

출력예제 1

3

 

예제설명

(2, 3) , (3, 5), (5, 7)이 회의실을 이용할 수 있다.

import sys

n = int(input())
meeting = []
for i in range(n):
    s, e = map(int, input().split())
    meeting.append((s,e))		# 튜플로 리스트에 저장
    
# meeting.sort() 튜플의 앞의 s값 즉, 시작시간으로 정렬됨. 우리는 끝나는 시간으로 정렬하길 원함 !
meeting.sort(key=lambda x: (x[1], x[0]))
#for x in meeting:
#	print(x)

cnt = 0
ep = 0		#endpoint, 선택한 회의의 끝나는 시간
for s, e in meeting:
    if s>=ep:
    	cnt += 1
    	ep = e
        
print(cnt)

⭐️ Point ! ⭐️

• (리스트).append((값1, 값2)) 
  입력 받은 값1과 값2를 튜플로 리스트에 저장
  
  
• (리스트).sort(key = lambda x:(x[1], x[0]))
  튜플의 뒤의 값으로 정렬

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이