BOJ - 1931

Kaydenna92·2022년 6월 28일
0

Algorithm

목록 보기
15/36

문제보기

# greedy algorithm -> 정렬을 하면 풀 수 있을 것 같음.


n = int(input())
room = []
for i in range(n):
    a, b = map(int, input().split()) # 회의 시작 시간, 회의 종료 시간
    room.append([a, b])

room.sort(key = lambda x: x[0]) 
# 회의 시작시간으로 먼저 정렬
# [[0, 6], [1, 4], [2, 13], [3, 5], [3, 8], [5, 7], [5, 9], [6, 10], [8, 11], [8, 12], [12, 14]]

room.sort(key = lambda x: x[1]) 
# 회의 종료시간 기준으로 한번 더 정렬
# [[1, 4], [3, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]


cnt = 1
end = room[0][1] # 회의 종료 시간.

# 회의의 최대 개수 구하는 핵심 코드
for i in range(1, n):
    if room[i][0] >= end: # 회의시작시간이 회의 종료시간보다 클 경우에만 실행
        cnt += 1
        end = room[i][1] # end를 해당 요소의 회의 종료시간으로 재할당하여 다시 반복

print(cnt)
profile
persistently

0개의 댓글