[알고리즘] 프로그래머스 요격시스템 // 그리디

https://school.programmers.co.kr/learn/courses/30/lessons/181188?language=cpp

프로그래머스

 

* 풀이

• 끝점기준 정렬
• 끝점에서 미사일발사
• 안되는경우( missile <= new_start ), 새로 미사일 발사, 미사일위치갱신

#include <bits/stdc++.h>
using namespace std;

bool cmp(vector<int> v1, vector<int> v2){
    return v1[1] < v2[1];
}

int solution(vector<vector<int>> targets) {
    int ret = 1;  // 첫 미사일
    int n = targets.size();
    
    sort(targets.begin(), targets.end(), cmp);
    
    int missile = targets[0][1];  // 첫 요격 지점
    
    for(int i = 1; i < n; ++i) {
        if(targets[i][0] >= missile) {  // 현재 미사일이 이전 요격 범위를 벗어난 경우
            missile = targets[i][1];  // 새로운 요격 지점
            ret++;
        }
    }
    
    return ret;
}