단속카메라 - level 3

해결방법

왜 2점 밖에 안주는지 모르겠지만 쉽지 않았다.

아이디어

예제

위의 그림은 예시를 그림으로 한 것이다. 그림을 보면 알 수 있듯이 겹치는 것들 중 진출 좌표(r[i][1])이 가장 작은 것이 가장 많이 겹치게 할 수 있다.
하지만 안 겹치는 선은 안 겹치는 선들 중 가장 처음 것을 기준으로 다시 몇개 겹칠 수 있는지 계산하면 된다.

알고리즘

1. r[i][0], r[i][1] 오름차순으로 정렬

2. 변수 end : i번째까지 중 가장 작은 r[i][1]
   $$ end\ =\ min(end,\ r[i][1]) $$

3. 만약 end < r[i][1]이면 answer증가시키고, end = r[i][1]해준다.
   $$ end\ =\ r[i][1] $$

Time Compexity

정렬은 O(NlogN)이고, 업데이트는 O(N)이므로
$$ O(NlogN + N) $$

전체 소스

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(vector<int> a, vector<int> b) {
    if(a[0] == b[0]) return a[1] < b[1];
    return a[0] < b[0];
}
int solution(vector<vector<int>> r) {
    int answer = 1;
    sort(r.begin(), r.end(), cmp);
    int end = r[0][1];
    for(int i = 0; i < r.size(); ++i) {
        if(end < r[i][0]) {
            answer++;
            end = r[i][1];
        }
        else end = min(end, r[i][1]);
    }
    return answer;
}