[BOJ] 1931 / 회의실 배정 / Python 파이썬

[BOJ] 1931 /회의실 배정 / Python 파이썬

[BOJ] 1931 /회의실 배정 / Python 파이썬

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

1931번: 회의실 배정

 

풀이

회의실을 배정 할 수 있는 경우 중 가장 좋은 조건을 선택하는 탐색 문제이다.

 

한번의 탐색 만으로 해답을 찾기 위해서는, 탐색을 하는 순서가 중요하다.

 

1. 회의실을 예약 할 수 있는 기회가 많이 주어지는 경우는, 이전 회의가 되도록 이른시간에 종료되는 경우이다.
2. 이른시간에 종료되는 회의 중에서도 빨리 시작하는 회의가 우선적으로 예약될 가능성이 높다.

 

위 두가지의 조건으로 미리 회의실 예약 시간을 정렬하여 탐색을 진행하였다.

 

N = int(input())

times = []

for _ in range(N):
    times.append(list(map(int, input().split())))

times.sort(key=lambda x: (x[1], x[0]))
res = 1
end = times[0][1]

for s, e in times[1:]:
    if s >= end:
        res += 1
        end = e

print(res)

※ 문제를 해결하기위해 생각한 논리의 근거가 명확하지 못하였다.

※ 요즘 다시금 게을러 진것같다. 서두르지말되, 게으르지 말자.

 

 

 

---

참고 블로그

https://suri78.tistory.com/26

[백준알고리즘] 1931번: 회의실배정 -Python