Swea D3. 화물 도크 Python 활동선택문제

활동 선택 문제 알고리즘

(1,4),(3,5),(1,6) ... (12,14)

회의 종료시간이 가장 빠른 회의를 먼저 선택하면 된다.

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

종료시간이 가장 빠른 회의를 찾자마자 확정 (1,4)

⇒ 이제 4시 이후로 부터 회의가 가능하다.

4시 이후에 가장 빨리 끝나는 회의 찾기 (5,7)

⇒ 이제 7시 이후로 회의가 가능

7 시 이후로 가장 빨리 끝나는 회의 찾기 (8,11)

⇒ 이제 11시 이후로 회의가능

11시 이후로 가장 빨리 끝나는 회의 (12,14)

⇒ 정답은 4회

문제 전략

1. 끝나는 시간을 기준으로 오름차순 정렬
2. 빠르게 끝나는 회의를 선택하여 확정한다.
3. 이후로 가능한 회의 중, 빠르게 끝나는 회의를 선택하여 확정한다.

'''
0~0시 까지 24시간
A 도크의 사용신청 확인
최대한 많은 화물차 +> 최대 몇개
매시 정각으로 표시됨
앞 작업 종료와 동시에 다음 작업 시작
~5시 와 5시~  가능
'''
def docker(s):
    for i in range(n): # 10개의 스케쥴 중
        arr[i][0]
t = int(input())
for tc in range(1,t+1):
    n = int(input())
    arr= [list(map(int,input().split())) for _ in range(n)] # s 시작 e 종료
    arr.sort(key=lambda x:x[1]) # 종료시간을 기준으로 정렬
    s = 0
    i = 0
    cnt = 0
    while s<=24:
        if i ==n:
            break
        if s <= arr[i][0]:
            s = arr[i][1]
            cnt += 1
        i += 1
    print(f'#{tc} {cnt}')