[알고리즘] 백준 1931 - 회의실 배정

문제

백준 1931 - 회의실 문제

접근

1. 먼저 접근한 방식은 끝과 시작시간의 차이를 정렬시켜서 그 순서대로 출력을 할 생각이였다. 하지만, 이렇게 할시 end 시간을 체크하는 방법이 떠오르지 않아서 말았다

2. 다시 생각했을때는 시작과 끝 시간에 대해서 오름차순정렬을 생각했다. 시작시간에 대해서 오름차순을 하고, 그 후에 끝시간에 대해서 오름차순을 하면 끝시간이 같더라도 시작시간에 대해서 이미 정렬되어 있기에 겹칠수 없다

3. 그 후에 마지막 회의의 끝시간을 비교해 가면서 count를 늘렸다

 

풀이

n = int(input())

time = []
for _ in range(n):
    s, e = map(int, input().split())
    time.append([s, e])

# 시작 시간 -> 끝시간 순차적으로 오름차순을 해준다. ( 끝시간이 같아도 시작시간으로 오름차순이 된다 )
time = sorted(time, key=lambda a: a[0])
time = sorted(time, key=lambda a: a[1])

lastMeeting = 0
count = 0

for i, j in time:
    if i >= lastMeeting:
        count += 1
        lastMeeting = j

print(count)