[SWEA] 5202 . 화물 도크

많이 배정하거나 선택하는 문제를 '활동 선택 문제(Activity Selection problem)'라고 한다.

이 문제가 그리디 알고리즘(탐욕알고리즘)의 전형적인 문제라고 한다.

 

수식으로 그려봤을 때 겹치는 것들을 선택하면 안되는 문제이기 때문에

1. 종료되는 시간을 기준으로 정렬을 했다. sort()함수의 인자 안에 람다를 써주고 기준을 넣어주면 된다.( 리스트의 1번째가 종료시간이므로 x[1]이라고 해줬다.)

2. 다음 순서의 시작이 앞에 것의 종료시간 안에 있다면 그것을 제외시킨다.(pop(0)으로 표현)

3. 겹치지 않는다면 cnt ++해주고 end를 갱신시켜준다.

 

#cnt =1로 초기화한 이유는 제일 빨리 끝나는 것을 선택하고 시작하기 때문

---

T = int(input())

for tc in range(1,T+1):
    N = int(input())
    dock = [list(map(int, input().split())) for _ in range(N)]
    #끝나는 시간을 기준으로 정렬
    dock.sort(key=lambda x : x[1])
    
    cnt = 1
    end = dock.pop(0) #맨 처음꺼 뽑음

    #다음 시작이 앞의 끝나는 시간안에 있으면 삭제
    while dock:

        if dock[0][0] < end[1]:
            dock.pop(0)

        else:
            cnt +=1
            end = dock.pop(0) #갱신




    print("#{} {}".format(tc,cnt))