[Python] 백준 1931번 : 회의실 배정 (S2) - 그리디단계별2

#문제

www.acmicpc.net/problem/1931

1931번: 회의실 배정

#풀이 & 학습한 내용

"가능한 한 많은 구간을 선택하는 문제"입니다. 문제를 풀면서 프로그래머스의 단속카메라 문제(supremo7.tistory.com/161?category=873875)와 매우 유사하다고 느꼈습니다. 끝나는 시간 기준으로 오름차순 정렬을 한뒤에 끝나는 시간이 제일 빠른 앞부분부터 순서대로 살펴봐야 한다는 점이 같았습니다. 다만, 단속카메라에서는 끝나는 시간이 같았을 때의 정렬 기준이 상관없었지만, 이번 회의실 배정 문제에서는 끝나는시간이 같았을 때 시작시간 기준으로 오름차순 정렬을 해줘야 했습니다. (회의의 시작시간과 끝나는 시간이 같은 경우가 있기 때문에)

 

끝나는 시간으로 정렬하는 이유: kim6394.tistory.com/67

#소스코드 (12번째 줄 주목)

meets = [] #회의들 저장
meet_num = 0 #가능한 회의의 최대 개수
 
N = int(input())
 
for i in range(N):
    meet = tuple(map(int, input().split()))
    meets.append(meet) #튜플 형태로 회의 저장
 
#끝나는시간 기준으로 오름차순정렬
#★끝나는시간 같으면 시작시간 기준으로 오름차순정렬
meets = sorted(meets, key=lambda x: (x[1],x[0]))
#print(meets)
 
meet_num = 1 #정렬된 회의들에서 첫번째회의는 무조건 들어감
mini = meets[0][1] #첫번째회의의 끝나는시간
 
#마지막에 정답에 들어간 회의의 끝나는시간(mini)보다
#새로운회의의 시작시간이 크거나 같으면 정답구간으로 넣고
# mini값 갱신해준다
for i in range(1, N):
    if meets[i][0] >= mini:
        meet_num += 1
        mini = meets[i][1]
 
print(meet_num)

github.com/HoYoungChun/Algorithm_PS/blob/master/Greedy/BOJ_1931.py

HoYoungChun/Algorithm_PS