알고리즘: 백준 1932번 회의실 배정 (feat.Python)

백준 1932번 링크입니다. 

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

1931번: 회의실배정

 

최대 사용할 수 있는 회의의 수를 구하기 위해서는 

 

가장 빨리 회의가 끝나는 순으로 회의를 나열한다.

 

회의의 끝나는 시간을 오름차순으로 배열한 후

 

전 회의의 시작시간과 다음 회의의 끝나는 시간을 비교하여

 

리스트를 담는다. 

 

 

 

처음에 2차원 리스트의 두번째 요소만 배열하기 위해서 

 

이중 for문을 사용했지만 O(n) = n^2가 되기 때문에 

 

시간초과가 되었다. 

 

그래서 lambda x: x[1]를 key로 받아 sort 함으로써 문제를 해결하였다. 

 

import sys

input = sys.stdin.readline

n = int(input())
class_list = [[0] * 2 for _ in range(n)]


for i in range(n):

    a, b = map(int, input().split())
    class_list[i][0] = a
    class_list[i][1] = b


class_list.sort(key = lambda x: x[1])

my_choice = [class_list[0]]
prev_class = class_list[0][1]


for i in range(1, n):

    if class_list[i][0] >= prev_class:
    
        my_choice.append(class_list[i])
        prev_class = class_list[i][1]



print(len(my_choice))

 

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
4

Process finished with exit code 0