[정렬 문제] 백준 1931번: 회의실 배정

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

1931번: 회의실 배정

정렬과 그리디 알고리즘이 혼합된 문제다.

n = int(input())
lst = []
for i in range(n):
    elem = list(map(int,input().split()))
    lst.append(elem)

lst = sorted(lst, key= lambda x : (x[0], x[1]))

ans = 1
end = lst[0][1]
for i in range(1, len(lst)):
    start = lst[i][0]
    finish = lst[i][1]
    if finish < end: # overlap
        end = finish
    elif start >= end: # not overlap
        ans +=1
        end = finish
print(ans)

어? 이걸 어떻게 알아내지 생각하다가 

다음 회의가 뭐가 됐던 간에 일단 앞 회의의 끝나는 시간이 빠를 수록 좋을 것이다라는 생각을 했다.(그리디)

그래서 시간 정보를 담고 있는 리스트를 정렬해야 겠다는 생각을 했고

처음에는 x[1], 즉 끝나는 시간이 빠른 순서대로 정렬 해야하나 생각했지만 뭔가 아닌 것 같아서,

x[0]로 정렬을 해주었다.

 

답을 찾아낼 때 처음 생각한 방법은

1. 끝나는 시간이 제일 작은 걸 찾아서 end 변수에 저장

2. end보다 시작 시간이 큰 것중에 끝나는 시간이 제일 작은 걸 찾아서 end 변수에 저장

3. 이를 반복

근데 이렇게 계속 최솟값을 찾아야 되는 방식은 시간복잡도 O(n2)이라 풀기가 어려울 거라 생각했다.

 

그래서 최솟값을 min함수로 찾는 방식이 아니고 순차적으로 탐색하면서

end보다 종료 시간이 작은 걸 찾으면, end를 이 값으로 업데이트  <-- 시간표가 겹치지만 더 좋은 걸 찾았을 때

end보다 시작 시간이 더 큰 걸 찾으면 end를 업데이트하면서 ans +=1  <-- 시간표가 겹치치 않은 경우를 찾았을 때

이 방식으로 시간복잡도 n에 풀 수 있다.

 

끝!

 

++ 정렬을 x[1]로 해도 문제가 풀린다..!!

n = int(input())
lst = []
for i in range(n):
    elem = list(map(int,input().split()))
    lst.append(elem)

lst = sorted(lst, key= lambda x :(x[1], x[0]))

ans = 1
end = lst[0][1]
for i in range(1, len(lst)):
    start = lst[i][0]
    finish = lst[i][1]
    if finish < end: # overlap
        end = finish
    elif start >= end: # not overlap
        ans +=1
        end = finish
print(ans)