[백준/파이썬]1931 회의실 배정

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

1931번: 회의실 배정

문제

회의 시작시간과 끝나는 시간을 알려주고, 최대한 많은 회의가 가능한 횟수를 출력하는 문제다.

 

처음 접근 했던 방식은 시작 시간을 기준으로 정렬하고, 전체 회의 시간 중 하나를 기준으로 잡고 잡은 기준으로 회의를 시작했을 때, 몇 번의 회의를 할 수 있는지 카운트하는 방식으로 풀었었다.

 

n = int(input())

arr = []

for i in range(n) :
    arr.append(list(map(int, input().split())))

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

mmax = -1

for i in range(n) :
    count = 1
    last_point = arr[i]
    for j in range(i,n) :
        if i == j :
            continue
        if last_point[1] <= arr[j][0] :

            count += 1
            last_point = arr[j]

    if count >= mmax :
        mmax = count

print(mmax)

이렇게 풀었는데 시간 초과가 났다.

 

그래서 다른 방법으로 끝나는 시간으로 정렬 후 풀었다.

 

끝나는 시간을 기준으로 정렬하면 위에 처럼 하나를 기준으로 잡고 하나하나 반복을 돌려보지 않아도 된다.

 

단, 주의 할점은 정렬을 할 때, 끝나는 시간으로만 정렬을 하면 안 된다. 정렬의 조건을 두 개로 해야 한다. 끝나는 시간이 같을 땐 시작하는 시간을 기준으로 정렬해야 한다.

 

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

 

정답

n = int(input())

arr = []

for i in range(n) :
    arr.append(list(map(int, input().split())))

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

et = 0
count = 0
for i in range(n) :
    if arr[i][0] >= et :
        count += 1
        et = arr[i][1]
print(count)