단속카메라

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

programmers 프로그래머스

우선 오름차순 정렬시켜준다.

모든 좌표를 (x, y)라고 생각하자. 2차원이 아니라 일직선 위에서 좌표를 단순히 표시하는 것임.

그 다음 나올 좌표는 (routes[i][0], routes[i][1])이다.

어차피 오름차순 정렬되어 있기 때문에 routes[i][0]은 x보다 무조건 크거나 같다.(작을 수는 없다.)

그래서 중요한 것은 그 전의 좌표(x, y)에서 y가 중요하다.

y를 routes[i][0]과 비교해야한다.

y < routes[i][0]일 경우에는 아예 겹치지 않으므로, 카메라를 1대 설치해야 한다.

이때, y는 routes[i][1]로 갱신해야한다.

그게 아니라면 좌표(x, y)에 routes[i][0]이 있으므로 겹친다. 즉, 카메라를 굳이 설치할 필요가 없다.

이때의 y는 더 작은 것으로 갱신해야한다. y = min(y, routes[i][1])

더 큰 것으로 갱신해버리면, y는 계속 커지므로, 좌표 (x, y)에 않에 겹치지 않은 선분들이 있을 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
 
int solution(vector<vector<int>> routes) {    
    int answer = 1;
 
    sort(routes.begin(), routes.end());
 
    int x = routes[0][0], y = routes[0][1];
 
    for (int i = 1; i < routes.size(); i++) {        
        if (y < routes[i][0]) {
            ++answer;
            y = routes[i][1]; // 첫 제출에 이 부분을 빼먹었다. 아예 겹치지 않으니, y를 갱신해야함.
        }
        else {
            y = min(y, routes[i][1]);
        }
    }
 
    return answer;
}
 
int main()
{
    cin.tie(0);
 
    /*vector<vector<int> > v = {
        {-20, 15},
        {-14, -5},
        {-18, -13},
        {-5, -3}
    };*/
 
    vector<vector<int> > v = {
        { 1, 3 },
        { 4, 5 },
        { 5, 7 }
        // 답 2
    };
 
    printf("%d\n", solution(v));
 
    return 0;
}