프로그래머스 - 단속카메라

프로그래머스 - 단속카메라

먼저 구간을 오름차순으로 정렬해놓고, 아직 겹쳐지지 않은 구간들에 대해서 앞에서부터 최대한 많이 겹쳐주면서 answer를 1씩 증가시켜주면 된다.
이 때, 겹칠때마다 left와 right가 바뀔 수 있으니 이를 갱신해줘야한다.

코드는 다음과 같다.

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 0;
    
    sort(routes.begin(), routes.end());
    vector<int> visited(routes.size(), 0);
    for(int i=0;i<routes.size();i++) {
        if(visited[i])
            continue;
        answer++;
        int l = routes[i][0];
        int r = routes[i][1];
        for(int j=0;j<routes.size();j++) {
            if(visited[j])
                continue;
            if(routes[j][1] < l || routes[j][0] > r)
                continue;
            l = max(l, routes[j][0]);
            r = min(r, routes[j][1]);
            visited[j] = 1;
        }
    }
    
    return answer;
}