문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42884


푼 풀이



풀이방식은 각 time stamp별로 가장 많은 차량있는 time stamp를 확인하고

그 구간에 카메라를 설치

카메라에 커버되는 차량들을 routes에서 제거


로 풀었는데 테스트케이스 2개를 통과못하네요..

그리디로 풀었는데 그리디 조건(가장 많은 차들이 있는 구간에 카메라를 설치) 이 이게 맞는지, 

맞다면 어떤 케이스를 고려를 못했는지 잘 모르겠습니다.


def solution(routes):

    camera = 0

    

    while routes:

        ### get all time stamps

        in_ts, out_ts = [], []

        for it, ot in routes:

            in_ts.append(it)

            out_ts.append(ot)

            

        ### for all time stamps, find max congestion time

        car, max_count = 0, -1

        for ts in sorted(in_ts+out_ts): 

            if ts in in_ts:

                car += 1

            if car > max_count:

                max_count = car

                peak_time = ts

            if ts in out_ts:

                car -= 1

                

        ###install camera

        camera += 1

        

        ### remove route covered by camera

        for r in routes[:]:

            if r[0] <= peak_time and r[1] >= peak_time:

                routes.remove(r)

                

    return camera

        


print(solution([[-2,-1], [1,2],[-3,0]])) #2

print(solution([[0,0],[-1,0],[0,0],[2,3],[0,0]])) #1

print(solution([[0,1], [0,1], [1,2]])) #1

print(solution([[0,1], [2,3], [4,5], [6,7]])) #4

print(solution([[-20,-15], [-14,-5], [-18,-13], [-5,-3]])) #2

print(solution([[-20,15], [-14,-5], [-18,-13], [-5,-3]])) #2

print(solution([[-20,15], [-20,-15], [-14,-5], [-18,-13], [-5,-3]])) #2



고수님들 도와주세요..