그리디 알고리즘> 1931. 회의실배정

 

<문제링크: www.acmicpc.net/problem/1931>

1931번: 회의실배정

문제설명: N개 회의가 주어지고 각각의 시작시간과 종료시간이 주어진다.

한 개의 회의실로 최대한 많은 회의를 할 수 있도록, 회의시간이 겹치지 않게 배정하는 방법을 생각해야 한다.

 

 

[1차 시도]

N = int(input())
timetable = [list(map(int,input().split())) for _ in range(N)]

timetable.sort()
ans = 1
minV = 2**31

for i in range(len(timetable)):

    if timetable[i][1] < minV:
        minV = timetable[i][1]
        
    else:
        if timetable[i][0]>= minV:
            ans+=1
            minV = timetable[i][1]
            
print(ans)

 

풀이: 회의 개수 N과 회의 시간들을 담을 timetable 변수를 만든다

 

timetable의 회의 시작시간을 기준으로 회의들을 오름차순 정렬한다.

ans는 최소 한 개의 회의를 배정할 수 있으므로 1로 저장한다.

종료시간이 제일 짧은 회의를 찾기 위한 minV를 문제 조건의 최대 시간으로 저장한다.

 

timetable을 for문으로 돌며 회의 종료시간이 현재의 최소 종료시간(minV)보다 작다면,

minV를 현재 회의 종료시간으로 갱신한다. 

 

만약 현재 회의 종료시간이 최소값보다 크다면, 바로 앞의 회의가 회의실을 배정받았으므로,

따라서 현재 회의 시작시간과 앞 회의의 종료시간을 비교하며 회의 시작시간이 더 클때까지 반복한다.

 

ex) 1  4    - 바로 앞에서 회의실 배정 받은 회의

     2  13   

     3  5

     3  8    ...반복

     5 9    - 앞 회의 종료시간(4) 보다 현재 회의 시작시간(5)이 클 때 멈춘다.

 

그러면 현재 회의도 배정이 가능하므로 ans+1을 한다.

그리고 최소 종료시간은 다시 현재의 종료시간으로 갱신한다.

 

 

채첨결과: 제출하면 정상적으로 잘 통과한다.

 

 

 

 

'쫄보의삽질' 블로그 탄생 스토리가 궁금하다면:

Git push 취소 방법 (feat. '쫄보의삽질' 블로그 탄생 배경)