[백준] 1931. 회의실 배정 python

문제 링크 : 1931번 회의실 배정

1931번: 회의실 배정

풀이 코드 : GIthub

문제

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

 

풀이

첫 번째 풀이

코드

count  = 1
for t in diff_list:
    meeting_start = map_int[t[1]][0]
    meeting_end = map_int[t[1]][1]
    flag = False

    for meeting in meeting_list:
        if ((meeting[1] > meeting_start and meeting[0] < meeting_start) or 
        (meeting[1] > meeting_end and meeting[0] < meeting_end) or 
        (meeting[0] < meeting_end and meeting[0] >= meeting_start) or 
        (meeting[1] >= meeting_end and meeting[1] < meeting_start)):
            flag = True
            break
    if flag:
        continue
        
    meeting_list.append(map_int[t[1]])
    count += 1

1. 회의시간이 짧은 순서대로 정렬하고 

2. 정렬한 순서대로 회의시간이 겹치지 않으면 회의표에 넣어 그 수를 카운트 함

• 겹치지 않음은 다음과 같다.
  • 회의의 시작시간과 끝 시간의 지금까지의 회의표에 있는 회의들의 시작시간과 끝시간 사이에 있지 않는다. 

새로운 회의가 회의표에 들어오는 경우

새로운 회의가 회의표에 들어오지 못하는 경우

 

 

• 그러나 아래와 같은 예외를 처리하지 못했다.

시작 시간과 끝나는 시간이 같은 회의가 새로운 회의의 시작 or 종료시간과 겹칠경우 겹친다고 판단을 한다.

 

• 문제에서는 회의시간의 시작과 종료시간이 같을 수 있다.(2시 시작 2시 종료)
• 그런데 기존 2시 시작 2시 종료의 회의가 있고 여기에 2시에 시작하는 회의가 들어오려고 한다면 위 코드는 이 두 시간이 겹친다고 판단하여 새로운 회의로 넣지 않는다. 

 

그래서 문제를 해결하지 못하였다.

 

 

 

두 번째 풀이(정답)

https://hei-jayden.tistory.com/33블로그의 풀이를 참고하여 문제를 해결하였다.

[백준 파이썬] # 1931 회의실 배정

 

코드

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

count = 1

meeting_end = time[0][1]

for i in range(1, N):
    if time[i][0] >= meeting_end:
        count += 1
        meeting_end = time[i][1]


print(count)

 

생각보다 단순하게 해결할 수 있었다.

 

그저 단순하게 끝나는시간으로 오름차순 정렬 끝나는 시간이 같으면 시작하는 시간으로 정렬한다.

그리고 단순히 회의를 채워 나가면 count를 한다.

 

 

그리디 문제의 경우 조금 더 단순하게 생각할 필요가 있을것 같다.