[그리디] 회의실 배정

📍 그리디 알고리즘

단계 별로 가장 좋은 것을 선택하는 알고리즘.
정렬하여 차례차례 선택해 나가면 된다.

1. 현재 상태에서 가장 좋은 것을 선택
2. 문제 조건을 만족하는지 검사
3. 원래 문제가 해결되었는지 검사, 해결되지 않았다면 다시 1번으로 돌아가 반복한다.

 

 

📌

# problem: https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8

 

 

<input>

5

1 4

2 3

3 5

4 6

5 7

 

 

# solve:

1. 종료시간이 가장 빠른 회의 순서대로 나열한다.

2. 끝나는 시간==시작하는 시간이면 사용할 수 있는 회의+=1 을 한다.

 

 

✔️ code

n=int(input())
meeting=[]

for i in range(n):
    s, e=map(int, input().split())
    meeting.append((s, e))

#정렬 순위 종료시간->시작시간
meeting.sort(key=lambda x: (x[1], x[0]))
et=0    #끝나는 시간
cnt=0	#회의 수
for s, e in meeting:
    if s>=et:
        et=e
        cnt+=1
print(cnt)

 

 

>>>

 

처음에 정렬 기준을 시작 시간으로 해서 원하는 답이 나오지 않고 코드가 굉장히 복잡해졌다.

회의가 빨리 끝나야 더 많은 회의를 할 수 있다는 걸 깨닫을 때까지 굉장히 오래 걸렸다 --;; 단순한데..