[프로그래머스][LV2][C++]요격 시스템

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

그리디하게 접근하는 것이 중요하다. 

핵심은 end포인트를 기준으로 오름차순 정렬하고 설정된 end포인트보다 Start 포인트가 작은 미사일은 요격해주고 아닌 경우에는 요격포인트를 새로 설정해주는 것이다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//그리디하게 접근
bool cmp(vector<int> &a,vector<int> &b){
    if(a[1]==b[1]) return a[0]<b[0];
    else return a[1]<b[1];
}
int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(),targets.end(),cmp);
    int end=targets[0][1];
    answer++;
    for(int i=1;i<targets.size();i++){
        //만약 시작값이 설정해둔 끝점보다 작다면 요격가능
        if(targets[i][0]<end) continue;
        //아니라면 새로운 요격포인트 지정
        else{
            answer++;
            end=targets[i][1];
        }
    }
    return answer;
}