백준-1931-회의실 배정

1. 문제 출처

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

1931번: 회의실 배정

2. 풀이

제일 회의가  빨리 끝나는 순으로 생각해주는 그리디 알고리즘 문제이다.

 

import sys
# 입력받기
n = int(sys.stdin.readline())
greedy_list = []
for _ in range(n):
    start , end = map(int,sys.stdin.readline().split(" "))
    greedy_list.append((start,end))

# 끝나는 시간을 기준으로 정렬
# 이때 끝나는 시간이 같ㅇ을 경우 시작하는 시간으로 정렬해야 한다.
# 왜냐하면 2 4 와 4 4 의 경우 4 4 가 먼저와 2 4가 스킵될 때와 같이
# 끝나는 시간이 같아 넘어가는 경우가 있기 때문이다.
greedy_list.sort(key = lambda x : (x[1],x[0]) )
count = 1
start,end = greedy_list[0]

if n > 1:
    # 전 회의 끝나는 시간 보다 같거나 뒤인 시작 시간이 있는 경우
    # 해당 회의 시간을 전회의 시간으로 업데이트 한다. 
    for s,e in greedy_list[1:]:
        if s < end:
            continue
        if s >=end:
            count+=1
            end = e
            
print(count)