[백준] 1931번 - 회의실배정

문제 링크 : www.acmicpc.net/problem/1931

1931번: 회의실배정

그리디 문제로 최대 테스트 케이스가 100000개이므로 최대 O(nlogn)알고리즘으로 작성해야 될 것 같았다.

 

회의가 끝나는 시간에 대해서 오름차순으로, 끝나는 시간이 같은 부분에서는 시작하는 시간에 대해서 오름차순으로 정렬하도록 하였다. 이를위해 sort()를 이용한 다중정렬을 이용하였다.

import sys

N = int(sys.stdin.readline())

meetings = []
for _ in range(N):
    tp = tuple(map(int, sys.stdin.readline().rstrip().split())) # (start, end)
    meetings.append(tp)

meetings.sort(key=lambda tp: (tp[1], tp[0]))
result = 0
end_time = 0
for meeting in meetings:
    start_time = meeting[0]

    if start_time >= end_time:
        end_time = meeting[1]
        result += 1

print(result)