회의실 배정

풀이

 1개의 회의실에 회의가 겹치지 않게 최대한 많은 회의를 배정해야 한다. 이때는 그리디 알고리즘을 적용해야 하는데, 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는 데 유리하다. 그렇기 때문에 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택하면 이 문제를 해결할 수 있다.
 주의할 점은 문제의 조건을 잘 봐야 한다. "회의의 시작 시간과 끝나는 시간이 같을 수도 있는데, 이때는 시작하자마자 끝나는 것으로 생각하면 된다"의 조건에 따라 종료 시간순으로 정렬한 후 만약 종료 시간이 같을 때는 시작 시간을 기준으로 다시 한번 정렬해야 한다.

import sys
N = int(input())
data = []
for i in range(N):
    data.append(list(map(int, sys.stdin.readline().split())))

data.sort(key=lambda x: (x[1],x[0]))
first = data[0]
count = 1
for i in range(1, N):
    if first[1] <= data[i][0]:
        first = data[i]
        count += 1
print(count)

시간복잡도 : O(NlogN)