백준(baekjoon) 1931번: 회의실 배정(실버 1, 파이썬 PYTHON) - 그리디 알고리즘

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

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

1931번: 회의실 배정

 

import sys

N=int(sys.stdin.readline())
schedule=[list(map(int,sys.stdin.readline().split())) for _ in range(N)]
count=1

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

end=schedule[0][1]

for x in range(1,N):
  if(schedule[x][0]>=end):
    count+=1
    end=schedule[x][1]
  else:
    continue

print(count)

 

※ 그리디 알고리즘

 

 

● 먼저 회의의 수 N을 입력받은 후, 그 후 N개의 줄에 들어오는 각 회의의 시작시간과 끝나는 시간을 list에 담아서 schedule 배열에 넣어준다. 그리고 사용할 수 있는 회의의 수를 계산할 초기값 1인 변수 count를 선언해준다.

 

● 회의를 최대로 사용하려면 회의가 끝나는 시간이 이른 회의를 우선적으로 선택하여야 그 뒤에 선택할 수 있는 회의의 폭이 넓어진다. 그러므로 각 회의가 끝나는 시간을 기준으로 오름차순 정렬을 진행한다. 그런데 회의가 시작하는 시간과 끝나는 시간이 같을 수도 있다 하였으므로 회의가 끝나는 시간을 기준으로 오름차순 정렬을 진행하기 전에 각 회의가 시작하는 시간을 기준으로 먼저 오름차순 정렬을 진행해 주어야 한다. 예를 들어 회의 A는 시작하는 시간과 끝나는 시간이 모두 2, 회의 B는 시작하는 시간이 1, 끝나는 시간이 2라고 하면 회의 A가 회의 B 앞에 있으면 회의 A를 먼저 선택하면 B는 선택할 수 없지만, 끝나는 시간은 같지만 시작하는 시간이 더 이른 회의 B를 앞에 두면 두 회의를 다 선택할 수 있기 때문이다.

 

● 이제 schedule은 정렬된 상태이다. 맨 처음에 schedule배열에 들어있는 첫 회의 정보를 선택할 것은 확실하기 때문에 count를 1로 설정하였고, 이 회의의 끝나는 시간을 초기값으로 하는 변수 end를 선언해준다.

 

● for문의 x는 1부터 N-1 까지의 값을 가진다. 현재 단계에서 보고있는 회의의 시작 시간이 지금 end에 담겨있는 값보다 크거나 같다면(schedule[x][0]>=end), 이 회의는 사용할 수 있으므로 count값을 1 올려주고 end 값을 이 회의의 끝나는 시간인 schedule[x][1]로 갱신해준다. 만약 현재 단계에서 보고있는 회의의 시작 시간이 지금 end에 담겨있는 값보다 작다면 이 회의는 선택될 수 없으므로 다음 회의로 넘어갈 수 있도록 한다.

 

● for문을 빠져나온 뒤 count를 출력해주면 답을 구할 수 있다.