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

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

프로그래머스

 

해결 방법

• 진출 지점이 앞부분인 차량순으로 정렬한다. (routes[a][1] < routes[b][1] )
• 맨 앞 차부터, 나갈때 단속카메라를 설치한다. 즉, routes[i][1] 부분에 감시카메라를 설치한다.
• 만약 현재 설치된 카메라지점안에 차량이 있다면, 즉, 진입부분이 카메라보다 앞에 있다면, 카메라를 설치할 필요가 없으므로 그냥 넘어간다. 
• 만약 현재 카메라지점에 내 차량이 포함되지 않는다면 , 내 진출부분에 카메라를 설치한다.

 

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

using namespace std;

bool compare(vector<int>& a, vector<int>& b){
    return a[1]<b[1];
}

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end(), compare);
    
    int route = -99999;
    for(int i=0; i<routes.size(); i++){
        if(route < routes[i][0]){
            answer ++;
            route = routes[i][1];
        }
    }
    
    return answer;
}