백준 1931 - 회의실 배정

문제

알고리즘 분류)

• 그리디 알고리즘
• 정렬

풀이

N개의 회의가 주어진다, 각 회의는 시작시간과 끝나는시간이 주어지고
주어진 회의를 최대 몇개 진행할 수 있는지 묻는 문제이다

핵심 : 가장 빨리 끝나는 회의부터 진행한다

가장 빨리 끝나는 회의순으로 정렬하여
최소 1개 회의는 무조건 진행할 수 있으므로 카운트는 1부터 시작이다
루프를 이용하여 현재 탐색중인 회의의 시작시간이 앞에서 진행한 회의의 끝나는 시간보다 빠르면(작으면)
패스한다
그렇지 않으면 회의를 진행할 수 있으므로 카운트를 더해주고
이전 회의의 끝나는 시간을 저장해둔다

소스코드

python)

import sys
N = int(input())
array=[]
for _ in range(N):
    array.append(list(map(int,sys.stdin.readline().split())))
    
array.sort(key=lambda x:(x[1], x[0]))

prev_finish = array[0][1]
cnt = 1

for i in range(1,N):
    start = array[i][0]
    
    if start < prev_finish:
        continue
    else:
        cnt += 1
        prev_finish = array[i][1]
        
print(cnt)