2022.02.14 [백준] (python 파이썬) 회의실 배정

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

---

풀이

이 문제를 보고 처음 아래와 같이 코드를 작성했을 때, 각 시간을 arr에 입력 받고 시작시간으로 오름차순 정렬하고 시간이 같을 시, 종료시간을 오름차순으로 정렬했다. 

그리고 이중 for문을 돌려 각 인덱스별로 시작했을 때의 최대 회의 수를 count배열에 넣고 max함수를 이용해 최대값을 출력했다. 그러나 시간초과가 발생했다....O(N^2)이라서 그런거같다....그래서 시간복잡도를 어떻게 줄일까 하면서 생각해보았다. 그러다 모든 회의에 대한 최대값을 구할 필요가 없다고 생각이 들었다. 왜냐하면 arr배열을 종료시간으로 우선 오름차순 정렬하고 값이 같을 시, 시작시간으로 오름차순 정렬하면 첫번째 인덱스 값이 종료시간이 가장 빨라 고정이 되기 때문이다. 그래서 밑의 정답코드로 작성하게 되었다.

import sys
 
input=sys.stdin.readline
arr=[]
for _ in range(int(input())):
    arr.append(list(map(int,input().split())))
 
arr.sort(key=lambda x:(x[1],x[0]))
cnt=1
end=arr[0][1]
for i in range(1,len(arr)):
    if end<=arr[i][0]:
        end=arr[i][1]
        cnt+=1
print(cnt)