[백준 알고리즘/python] 백준 1931번 회의실배정, 파이썬 설명

백준 알고리즘의 그리디 파트, 1931번 회의실배정 문제를 파이썬코드와 함께 내가 이해한대로 설명해보려 한다.

 

문제 출처

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

1931번: 회의실배정

 

먼저 그리디라는 알고리즘은 그냥 당장 단순하게 좋은것만 생각하는 알고리즘이다.

따라서 이후의 상황은 그냥 고려하지 않는 알고리즘이다.

문제를 잘 읽어 보고, 그리디를 써야겠다는 생각이 들 때 까지 익숙해져야 한다.

 

문제 해석

#1. N개의 회의에 대해 회의실 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고 각회의가 겹치지 않게 회의실 사용 표를 만들어라

#2. 단 회의 시작시간과 끝나는시간이 같을수는 있다.

 

#생각

#1. 이 문제에 가장 큰 힌트는 끝나는 시간에 있다. 끝나는 시간이 빠른 순으로 정렬을 한다.

#2. 이후에 다음 회의의 시작시간과 전 회의의 끝나는 시간이 겹치지 않으면 카운트를 해 준다.

 

문제 자체는 간단한 문제이다.

생각에 대한 내 코드이다.

 

import sys

N = int(sys.stdin.readline())
lst = list()
for i in range(N):
    lst.append(list(map(int,sys.stdin.readline().split())))

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

cnt = 1
last_end_time = lst[0][1]
for i in range(0,N-1):# 시작시간이 처음의 끝시간보다 작으면 안됨
    if last_end_time <= lst[i+1][0]:
        cnt = cnt + 1
        last_end_time = lst[i+1][1]

print(cnt)

 

중간에 있는 sort 부분은 이차원 리스트 형태로 받아온 자료에 대해서, 1번 인덱스 먼저 정렬 후 , 0번 인덱스로 정렬한다는 의미이다.