[프로그래머스] 단속카메라

[프로그래머스] 단속카메라

문제 링크

#include <string>
#include <algorithm>
#include <vector>

using namespace std;
int solution(vector<vector<int>> routes) {
    int answer = 1;
    sort(routes.begin(), routes.end());
    int n = routes.size();

    int start = routes[0][0];
    int end = routes[0][1];
    for(int i=1; i<n; i++){
        if(start <= routes[i][0] && routes[i][0] <= end){
            start = max(start, routes[i][0]);
            end = min(end, routes[i][1]);
        }else{
            start = routes[i][0];
            end = routes[i][1];
            answer++;
        }
    }
    return answer;
}

• 가장 많이 겹치는 범위를 update를 해주면 된다.
• 범위는 start, end로 결정한다. answer의 초깃값을 1로 설정해준다.
• 들어온 지점의 순서대로 sorting을 해 준다.
• 차의 갯수만큼 반복문을 돌면서, 들어온 차가 범위 안에 있으면 범위를 update 해 주고,
• 아니라면 범위를 해당 차로 초기화 시켜준 후 새로운 차를 기준으로 반복문을 진행한다. (그리고 감시카메라를 +1 한다.)