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

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42884
알고리즘 : 그리디

핵심

카메라의 위치에 따른 차량 위치를 생각해야 함.
1. 차량 진출이 빠른 시점으로 전부 정렬
2. 차량이 진입했을때 마지막으로 설치한 카메라의 위치가 진입보다 뒤에 있다면 카메라의 갯수를 늘리고 해당 차량의 진출 시점에 마지막으로 설치한 카메라를 설치해야함.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int solution(vector<vector<int>> routes) {
    // 1. 차량의 진출 지점 기준으로 정렬
    // 기준점을 람다로 한다. 이때 a, b를 추가함으로써 현재 a, b의 진출 지점을 비교하여 sort
    sort(routes.begin(), routes.end(), [](const vector<int> a, const vector<int> b) { return a[1] < b[1]; });

    int cameras = 0;
    // 최저 진입지점 이여야 카운팅 시작
    int last_camera = -30001;

    for (const auto &route : routes) {
        int start = route[0];
        int end = route[1];

        // last_camera = -55, 진입을 -52부터 해버리면 탐색 불가
        if (last_camera < start) {
            cameras++;
            // 카메라는 진출 시점까지로 확대
            last_camera = end;
        }
    }

    return cameras; // 최소 카메라 수 반환
}