그리디 알고리즘

하나의 회의실이 있고 n개의 회의가 열릴 계획이 있을 때,

최대 몇 개의 회의를 배정할 수 있는지 구해보자.

 

n=int(input())
list=[]		# 각 회의의 시작 시간과 끝 시간
for i in range(n):
    s, e=map(int, input().split())
    list.append((s, e))		# 튜플 형태
list.sort(key=lambda x : (x[1], x[0]))	# list의 자료를 하나(x) 받아서 x[1]이 우선순위, x[0]이 차순위로 정렬
et=0		# 현재 회의가 끝나는 시간
cnt=0
for s, e in meeting:
    if s>=et:
        et=e 
        cnt+=1
print(cnt)

 

각 회의의 (시작 시간, 끝나는 시간)을 리스트에 저장한다. 종료 시간이 빠른 회의부터 배정하는 것이 유리하므로, x[1] (종료 시간) 기준으로 정렬한다. 종료 시간이 같다면 x[0] (시작 시간) 기준으로 정렬한다.

 

1. 현재 진행 중인 회의의 끝나는 시간을 et(End Time)으로 설정하고 이를 기준으로 새로운 회의를 배정한다.

2. 회의의 시작 시간(s)이 et보다 크거나 같을 경우에 배정한다.

3. 배정된 회의 개수(cnt)를 증가시킨다.

 

배정된 회의 개수를 출력한다.

 

배운 점.............2차원 리스트 정렬하는 법

arr = [[3, 2], [1, 4], [5, 1], [2, 3]]

arr.sort()	# 첫 번째 요소를 기준으로 정렬
# [[1, 4], [2, 3], [3, 2], [5, 1]]

arr.sort(key=lambda x:x[1])	# 두 번째 요소를 기준으로 정렬
# [[5, 1], [3, 2], [2, 3], [1, 4]]

arr.sort(key=lambda x:x[1], reverse=True)	# 두 번째 요소를 기준으로 내림차순 정렬
# [[1, 4], [2, 3], [3, 2], [5, 1]]

 

그리고 두 개 이상의 기준으로 정렬하는 방법이 있다.

arr = [[3, 2], [1, 4], [5, 1], [2, 3], [3, 1]]

arr.sort(key=lambda x:(x[0], x[1]))
# [[1, 4], [2, 3], [3, 1], [3, 2], [5, 1]]
# 첫 번째 요소(x[0])를 기준으로 오름차순 정렬
# 첫 번째 요소가 같으면 두 번째 요소(x[1])를 기준으로 오름차순 정렬

arr.sort(key=lambda x:(-x[0], -x[1]))
# [[5, 1], [3, 2], [3, 1], [2, 3], [1, 4]]
# -x[0]을 사용하면 첫 번째 요소를 기준으로 내림차순 정렬
# 첫 번째 요소가 같으면 두 번째 요소(-x[1])를 기준으로 내림차순 정렬