프로그래머스 level3 단속 카메라 (python)

Problem

https://school.programmers.co.kr/learn/courses/30/lessons/42884#

Solution

def solution(routes):
	camera = []
    for start, end in sorted(routes):
        flag = False
        for idx, (c_start, c_end) in enumerate(camera):
            if c_start <= start <= c_end or c_start <= end <= c_end:
                camera[idx] = [max(c_start, start), min(c_end, end)]
                flag = True
        if not flag:
            camera.append([start, end])
    return len(camera)

카메라가 존재할 수 있는 범위를 기록하였다. 현재의 차의 start, end 지점과 겹치는 카메라 범위가 있다면 해당 카메라 범위를 업데이트하고, 없다면 차를 기준으로 [start, end]를 추가하였다.

카메라와 차의 범위가 겹치는 케이스는 2가지 이다

1. camera_start ≤ start ≤ camera_end ≤ end

   새로운 카메라 범위: start ~ camera_end

2. start ≤ camera_start ≤ end ≤ camera_end

   새로운 카메라 범위: camera_start ~ end

즉, 새로운 카메라 범위는 [max(camera_start, start), min(camera_end, end)]가 된다.

이후 카메라 범위의 개수가 설치해야 할 카메라의 개수이다.