백준 1931 회의실 배정

유형 : 그리디

 

빨리 끝나는 회의부터 처리해야 한다. 이때, 끝나는 시간이 똑같은 회의의 경우, 시작 시간이 빠른 회의부터 처리한다.

 

코드

import sys

n=int(sys.stdin.readline())
times = []
for _ in range(n):
    times.append(tuple(map(int,sys.stdin.readline().split())))
  
times.sort()
times.sort(key=lambda x: x[1])
now,ans=0,0
for time in times:
    if time[0]>=now:
        ans+=1
        now=time[1]
print(ans)

 

정렬

 위의 코드에서는 times.sort()로 회의 시작 시간을 기준으로 정렬을 한 후, 회의 종료 시간을 기준으로 한번 더 정렬을 함으로써 위에서 언급한 규칙을 만족시켰다.

 하지만, 아래와 같이 comparator를 직접 정의함으로써 한번에 정렬할 수도 있는데, 내장함수로 두번 정렬하는 위의 방법이 훨씬 효율적이었다. ( 위의 방법 : 메모리 44944kb, 시간 328ms, 아래의 방법 : 메모리 50360kb, 시간 552ms)

from functools import cmp_to_key

def compare(x, y):
    if x[1] < y[1] :
        return -1 
    elif x[1] > y[1] :
        return 1
    else: 
        if x[0] < y[0] :
            return -1
        else:
            return 1
times.sort(key=cmp_to_key(compare))

 

문제풀기

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