1931번 회의실 배정

1931번 회의실 배정

실버 I

💡문제 분석 요약

Greedy+sorting

💡알고리즘 설계

끝나는 시간이 빨라야, 더 많은 회의를 집어 넣을 수 있다.

따라서 끝나는 시간으로 우선 정렬하고, 끝나는 시간이 같을 경우 시작 시간이 빠른 것으로 정렬한다.

이후 끝나는 시간이 빠른 것부터 우선 넣고, 이후 넣을 수 있는 것을 차례차례 넣는다.

시작하는 시간,끝나는 시간을 묶어서 리스트에 넣고 끝나는 시간이 빠른 순서대로 정렬한다.

리스트를 돌면서 현재 회의가 끝난 시점을 나타내는 end_point와 회의 시작 시간을 비교한다. end point보다 시작 시간이 더 뒤인 경우(큰 경우) 회의를 할 수 있으므로 answer +=1하고, endpoint를 회의 끝나는 시간으로 변경한다.

💡코드

n= int(input())
item = []
for i in range(n):
    start,end = map(int,input().strip().split())
    item.append((start,end))
end_point= 0
answer = 0
item.sort(key = lambda x: (x[1],x[0]))
print(item)
for start,end in item:
    if end_point<=start: #끝나는 점이 시작 시간 보다 작으면
        answer +=1
        end_point=end #item의 끝나는 시간으로 바꾼다.
print(answer)

💡시간복잡도

N

💡 틀린 이유

정렬 조건을 다르게 했다. 차이로 나열해서 좀더 복잡하게 된 것 같다. start,end-start로 정렬했는데 이러면 문제는 끝나는 시간을 알 수 없으므로 시간 순서대로 배열 불가능하다.