백준 1931 회의실 배정 문제 python 풀이

회의실 배정


풀어봅시다

뭔소리지 싶다.

힌트 보니 이해간다.

본인이 스터디룸을 이용하는 사장님이라고 생각해보자.
일단 나에게는 최대한 많이 스터디룸을 배정시켜서 돈을 많이 버는게 목적이다.
손님들이 자기가 회의하고 싶은 시간대를 적어뒀으면
난 그걸 보고 최대한 많이 예약하기 위해 시간대를 최대한 촘촘하고 안비게 짜야 한다.
그리디와 정렬 알고리즘이다!

즉 오늘자 스터디룸 빌리실분? 하고 수를 세면
줄 선 사람들이 순서대로 자기들이 가능한 시간대를 적고 가고
관리자인 내가 그걸보고 최대한 많은 사람들이 이용하게 짜준다.

그럼 어떻게 해야할까?
종료시간이 빨라야 한다.
시작시간이 제일 빨라서 해줬더니 회의 10시간씩 하면 너무 손해임
그러니 일단 종료를 빨리 하는 사람들!
근데 종료 시간이 똑같으면 시작시간 늦은 사람부터 해야한다.
똑같이 회의가 2시에 끝나는데 한팀은 오전 10시 한팀은 오후 1시면 당연히 후자를 해야 한다.


N = int(input()) # 몇 명?
list = [] # 저장할 리스트

for i in range(N): # 출발 종료시간을 한명한명 받아줌
    start, end = map(int, input().split())
    list.append([start, end])

list.sort(key=lambda x:(x[1],x[0])) # 먼저 1번 인덱스 정렬, 그다음 0번 정렬

count = 1 # 예약 카운트  종료 시간이 제일 빠른애는 일단 등록하고 시작했으니 1부터

end = list[0][1] # 종료시간인 end 현재는 제일 첫 리스트
for j in range(1, N):
    if list[j][0] >= end: # 현재 비교하는 사람의 시작 시간이 현재 사람의 종료시간보다 같거나 늦다면
        count +=1 # 예약 하나 늘었고
        end = list[j][1] # 이제 현재 예약한 사람의 종료시간으로 바꿔줌
        
print(count)

끝입니다..^*^

좋은 웹페이지 즐겨찾기