백준 "회의실 배정" 문제
끝나는 시간 우선으로 오름차순 정렬 후 끝나는 시간이 같을시 시작시간도 오름차순으로 정렬해야한다.
처음에 끝나는 시간만 정렬했다가 실패했는데 질문에서 반례를 보고 고칠 수 있었다.
소스코드
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]))고친 결과는 다음과 같다.
Person