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

📖 문제 링크

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

📃 문제 설명

그리디 알고리즘을 이용하는 문제로

시작 시간과 끝나는 시간이 주어질 때 회의실을 이용할 수 있는 최대 횟수를 구하는 문제이다.

문제 설명에 적혀있는 "단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다." 부분이 까다로운 부분이였다.

회의 시작 시간과 끝나는 시간이 같을 수 있다는 것은

2
2 2
2 2

라면 출력이 2가 나와야된다는 것이다.

그래서 정렬을 할 때 빨리 끝나는 회의 순서대로 정렬을 해야한다.

🤔 예를 들어보자

4
0 9
3 4
4 5
5 9

이 경우를 보면 시작 순서로 정렬을 했을 때 0~9가 선택되게 되면 회의의 수는 1이 될 것이다.

반대로 끝나는 순서로 정렬을 하게 되면 3~4 4~5 5~9로 회의의 수가 3이 되는 것을 볼 수 있다.

물론 예외가 있다😨

3
7 9
2 2
1 2

이렇게 주어지고 끝나는 순서로 정렬되었을 때

7 9
2 2
1 2

로 정렬이 되고 회의의 수는 1~2가 무시되어 2번이 되게 된다.

그래서 정렬의 순서를
1. 끝나는 시간의 오름차순
2. 시작하는 시간의 오름차순
이렇게 두 순서로 해주어야 한다.

👨‍💻 문제 풀이

sort를 할 때 key로 인자 하나를 줄 수 있는 데
여러 인자를 주어 끝나는 시간, 시작 시간을 순서대로 정렬을 하도록 하였다!

N = int(input())

conferences = list()
count = 1

for info in range(N):
  conferences.append(list(map(int, input().split())))

conferences.sort(key=lambda x: (x[1], x[0]))
end_time = conferences[0][1]

for i in range (1, N):
  if (conferences[i][0] >= end_time):
    count += 1
    end_time = conferences[i][1]

print(count)

2021.08.21