백준 Python - 1931 회의실 배정

import sys
n=int(sys.stdin.readline())
arr1=list(map(int,sys.stdin.readline().split()))
cnt=1
for i in range(n-1):
    arr2=list(map(int,sys.stdin.readline().split()))
    if arr1[1]<=arr2[0]:
        arr1=arr2
        cnt+=1

print(cnt)

결과 : 틀렸습니다.

반례가 있나 본데 잘 모르겠다.

상황 : 

• 회의가 겹치면 안 된다. 
• 겹치지 않는 선에서 회의실 최대 사용 가능 횟수를 구하라
• 시작 시간과 끝나는 시간은 같을 수 있으며 끝나는 시간과 다음 회의 시작 시간은 중복 가능하다.

 

처음 arr1를 입력받고 arr2를 추가로 입력받으면서.

'다음 회의시간 시작 시간' - '이전 회의 끝나는 시간' >= 0

이므로 조건문에 부합하면 arr1=arr2 해준다.

어디서 틀린 거지?

---

입력받은대로 횟수를 구하는게 아니라 모든 입력에 대해서 최대 사용 가능 횟수를 구하는 거다. 문제를 제대로 못 봤다.

이렇게 되면 끝나는 시간을 기준으로 우선 정렬을 한 뒤 시작 시간으로 정렬해준다.

왜냐하면 

10 15

1   5

5   10

이렇게 있을 때 이대로 결과를 내면 회의가 1회 밖에 못하지만 정렬을 하면

1   5

5   10

10 10   

가 되어 총 3회가 가능하다. 

import sys
n=int(sys.stdin.readline())
s=[]
cnt=1
for i in range(n):
    s.append(tuple(map(int,sys.stdin.readline().split())))

#추가!
s.sort(key=lambda x:(x[1],x[0]))
t1=s[0]

for i in range(1,n):
    t2=s[i]
    if t1[1]<=t2[0]:
        t1=t2
        cnt+=1

print(cnt)

결과는 정답입니다.

맞았습니다!!

141120

424

PyPy3