Python/Greedy BOJ-1931 회의실 배정

Posted on | In

[Python/Greedy] BOJ-1931 회의실 배정

📌문제링크


하나의 회의실에서 최대로 회의를 할 수 있는 경우를 출력하면된다.

✔ 가장 중요한 포인트는 끝나는 시간, 시작하는 시간 순으로 오름차순 정렬을 하면된다.
아래 예시를 보면 (4,4) -> (1,4) 회의는 진행 할 수 없지만, (1,4) -> (4.4) 회의는 진행 할 수 있다.
(4,4)
(1,4)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
N = int(input()) # 회의의 수
TimeTable = []
for _ in range(N):
    start, end = map(int,input().split())
    TimeTable.append([start, end])

# 끝나는 시간, 시작시간 순으로 정렬
TimeTable = sorted(TimeTable, key = lambda x : (x[1],x[0]))

cnt = 1
end =TimeTable[0][1]
for i in range(N-1):
    if TimeTable[i+1][0] >= end :
        end =TimeTable[i+1][1]    
        cnt +=1

print(cnt)