[swea] 5202. 화물 도크 / python 파이썬

🚩 그리디

 

thinking

testcase 1

맨 처음 구간을 기준점으로 시작시간과 끝 시간을 비교하면서

8처럼 현재 시작시간이 전회차의 종료시간(14)보다 작으면(겹치면) 카운팅하지 않고,

17, 20, 23처럼 시작시간이 전회차의 끝시간(14, 20, 23) 보다 같거나 큰 경우에만 카운팅을 해주었다.

시간복잡도를 줄이기위해 pop(0) 대신 pop()을 사용할 수 있도록 input 리스트를

  1.작업완료시간 - 2.작업시작시간   순으로 내림차순으로 정렬했다.

# testcase `.sort(key=lambda x: (-x[1], -x[0])` 소팅결과

# testcase 1
[[23, 24], [20, 23], [17, 20], [8, 18], [4, 14]]

# testcase 2
[[20, 24], [12, 24], [21, 23], [14, 23], [1, 22], [2, 19], [15, 16], [6, 15], [6, 15], [1, 4]]

# testcase 3
[[23, 24], [20, 24], [9, 24], [20, 23], [16, 22], [13, 22], [17, 21], [5, 21], [18, 19], [13, 19], [13, 16], [11, 15], [7, 15], [2, 14], [2, 7]]

 

코드

T = int(input())

for tc in range(1, T+1):
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]
    a.sort(key=lambda x: (-x[1], -x[0]))

    s, e = a.pop()
    cnt = 1
    while a:
        c_s, c_e = a.pop()
        if e <= c_s:  # 현재 시작시간이 전회차의 끝시간보다 같거나 크면
            s, e = c_s, c_e  # 갱신
            cnt += 1

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