[파이썬 | SW Expert Academy] 화물 도크

[문제]

24시간 운영되는 물류센터에는 화물을 싣고 내리는 도크가 설치되어 있다.

0시부터 다음날 0시 이전까지 A도크의 사용신청을 확인해 최대한 많은 화물차가 화물을 싣고 내릴 수 있도록 하면, 최대 몇 대의 화물차가 이용할 수 있는지 알아내 출력하는 프로그램을 만드시오.

신청서에는 작업 시작 시간과 완료 시간이 매시 정각을 기준으로 표시되어 있고, 앞 작업의 종료와 동시에 다음 작업을 시작할 수 있다.

예를 들어 앞 작업의 종료 시간이 5시면 다음 작업의 시작 시간은 5시부터 가능하다.


[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 신청서 N이 주어지고, 다음 줄부터 N개의 줄에 걸쳐 화물차의 작업 시작 시간 s와 종료 시간 e가 주어진다.

1<=N<=100, 0<=s<24, 0 ＜ e ＜= 24 


[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

 

[풀이]

 

알고리즘 분류 : 그리디 

유명한 그리디 알고리즘 문제중 하나이다.

 

일단 종료 시간을 첫번째, 시작 시간을 두번째 기준으로 오름차순으로 정렬한다. (lambda 이용)

 

그리고 나서 일단 최소 종료시간을 찾은 뒤 그 작업을 수행한다. 그 다음 부터 탐색하면서, 현재 종료시간 보다 더 늦게 시작하는 시작시간이 있으면 해당 작업을 수행하는 알고리즘을 구성한다. 마지막으로 수행하는 작업의 종료시간을 end 변수에 저장시키면서 계속 비교할 수 있다.

 

T = int(input())
for t in range(1, T+1):
    
    N = int(input())
    tasks = []
    for _ in range(N):
        tasks.append(list(map(int, input().split())))
    tasks.sort(key = lambda x : (x[1], x[0]))
    
    ans = 1
    end = tasks[0][1]
    for i in range(1, N):
        if tasks[i][0] >= end:
            end = tasks[i][1]
            ans += 1
 
    print('#%d %d' % (t, ans))