[Level 3] 단속 카메라

 

겹치지 않는 범위는 어쩔 수 없이 카메라를 1대 주고, 겹치는 영역은 최대한 겹치도록 하면 된다.

비교를 위해 먼저 시작 지점을 기준으로 오름차순 정렬한다.

그다음 반복하면서 [i]와 [i+1]의 범위를 비교하여 [i+1]의 시작 지점이 [i]의 종료 지점보다 크면 겹치지 않는 것이므로 어쩔 수 없이 카메라 1대를 주고 넘어간다.

만약 [i+1]의 시작 지점이 [i]의 종료 지점보다 작거나 같다면 1칸이라도 겹치는 것이므로 새로운 영역의 시작 지점을 [i+1]의 시작 지점으로 업데이트한다. 종료 지점은 더 작은 지점으로 업데이트한다. 다음엔 이 새로운 영역과 비교해서 겹친다면 영역을 또 업데이트하던지, 겹치지 않는다면 현재까지의 영역에 카메라를 한 대주고, 다시 반복하면 된다.

 

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

using namespace std;

int solution(vector<vector<int>> routes) {
    
    // 시작 지점이 작은 순서대로 정렬
    sort(routes.begin(), routes.end(), [](const vector<int>& v1, const vector<int>& v2){
       return v1[0] < v2[0]; 
    });
    
    int curS = -1;
    int curE = -1;
    int answer = 0;
    for(int i = 0; i < routes.size(); ++i)
    {
        if(i + 1 == routes.size())
        {
            ++answer;
            break;
        }
        
        int s = (curS == -1) ? routes[i][0] : curS;
        int e = (curE == -1) ? routes[i][1] : curE;
        int nextS = routes[i+1][0];
        int nextE = routes[i+1][1];
        
        if(nextS <= e)
        {
            curS = nextS;
            curE = (e > nextE) ? nextE : e;
        }
        else
        {
            ++answer;
            curS = -1;
            curE = -1;
        }
    }
    
    return answer;
}