이숭간 공부기록

백준 1931번 파이썬 _ 회의실 배정 (실버2) 본문

알고리즘/백준

백준 1931번 파이썬 _ 회의실 배정 (실버2)

이숭간 2021. 3. 25. 15:40
728x90

www.acmicpc.net/problem/1931

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

  • 문제유형 : 그리디, 정렬

 

  • 문제풀이
    • 회의가 겹치지 않으면서 최대수를 구해야하므로 끝나는시작이 빠를수록, 끝나는 시작이 같다면 시작하는 시간이 빠를수록 해당 회의를 선택하는것이 최대의 회의개수를 만들수 있다. 
      • 시작시간으로도 한번더 정렬해줘야 하는 이유는 시작시간과 종료시간이 같은 회의일경우 count를 해줘야하기 때문이다.
    • 현재일의 시작시간이 이전일의 종료시간보다 크면 count를 증가시킨후, 종료시간을 현재일의 종료시간으로 갱신한다.
  • 정답코드 
import sys
input = sys.stdin.readline

n = int(input())
input_list = []
check = []

for i in range(n):
    input_list.append(tuple(map(int, input().split())))

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

count = 1
end_time = input_list[0][1]

for i in range(1,n):
    if input_list[i][0] >= end_time: #지금일이 시작시간이 앞의일의 종료시간보다 크거나 같으면 선택가능이므로
        count += 1
        end_time = input_list[i][1] #종료시간을 현재일의 종료시간으로 갱신

print(count)