#11 [python] 1931번: 회의실 배정

✔️ 그리디 알고리즘 이용해 회의의 최대 갯수를 출력

* 단 회의가 한 번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나느 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간과 끝나는 시간이 같을 수 도 있다 이경우는 시작하자마자 끝나는 것으로 생각하면 된다

-> 3 3 (회의 하나로 출력)

 

❗문제분석

1. 회의가 가장 많게 출력되려면 빨리 끝나는 회의 순서대로 정렬을 해야한다.// 이후 시간에 예약할 수 있는 여유가 많아짐 
2. 전체를 시작하는 시간의 오름차순으로 정렬 한 후, 끝나는 시간으로 오름차순 정렬

• end 기준 정렬만 이용 time = [(2 2),(1 2)]: cnt = 1
• end, start 기준 정렬 이용 time = [(1 2), (2 2)]: cnt = 2

 

*** 우선되는 정렬 기준을 나중에 입력

• a[1] & a[0]: a[0]을 우선 기준으로 정렬되고, a[1]이 차순 기준으로 정렬됨
• a[0] & a[1]: a[1]을 우선 기준으로 정렬되고, a[0]이 차순 기준으로 정렬됨

 

 

+ lambda 함수

lambda 인자 : 표현식

i) def 함수 사용 시

def add(x,y):
	return x + y

ii) 람다 함수 사용 시

add = lambda x, y: x + y

 

 

💫 코드

N = int(input())
time = []


for i in range(N):
    start, end = map(int, input().split())
    time.append([start, end])


time = sorted(time, key = lambda a : a[0]) # start 기준으로 오름차순 정렬   
time = sorted(time, key = lambda a : a[1]) # end 기준으로 오름차순 정렬

## 오름차순 정렬 시 시간복잡도 : O(NlogN)
## 2차원 요소를 기준으로 정렬할 때 sorted(list, key = lambda a:a[n]) 사용

last_end = 0
cnt = 0

for start, end in time:
    if start >= last_end:
        cnt += 1
        last_end = end

print(cnt)