튜플 정렬하기 [백준 1931번]

백준 "회의실 배정" 문제

끝나는 시간 우선으로 오름차순 정렬 후 끝나는 시간이 같을시 시작시간도 오름차순으로 정렬해야한다.
처음에 끝나는 시간만 정렬했다가 실패했는데 질문에서 반례를 보고 고칠 수 있었다.

소스코드

n=int(input())
timeline=[]
stack=[]
for i in range(n):
    s,e=map(int,input().split())
    timeline.append((s,e))

timeline.sort(key=lambda x:(x[1],x[0]))

stack.append(timeline.pop(0))

while timeline:
    time=timeline.pop(0)
    if stack[-1][1]<=time[0]:
        stack.append(time)

print(len(stack))   

처음에는

timeline.sort(key=lambda x:x[1])

이런식으로 끝나는 시간만 정렬했다. 이렇게 하면 다음 반례에서 이렇게 오답이 출력된다.(정답:5)

보면 (5,6)이 날아간걸 볼 수 있다. 시작시간을 정렬을 안해줬기때문에 (6,6)이 먼저 push되면서 (5,6)이 조건에 안맞아서 버려진것이다.
따라서 다음과 같이 시작시간도 정렬을 해줘야한다.

timeline.sort(key=lambda x:(x[1],x[0]))

고친 결과는 다음과 같다.

좋은 웹페이지 즐겨찾기