요격 시스템

Greedy로 풀 수 있는 문제.

단, [[0, 3], [1, 2], [2, 4]]와 같은 Case를 처리해주기 위해 Greedy 과정 중 기준 값 Update가 필요하다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(const vector<int> &a, const vector<int> &b)
{
    if (a[0] == b[0])
        return a[1] < b[1];
    return a[0] < b[0];
}
int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(), targets.end(), compare);
    
    for (int i=0;i<targets.size();i++) {
        int val = targets[i][1];
        int idx = i + 1;
        while (1) {
            if (idx >= targets.size())
                break;
            if (val <= targets[idx][0])
                break;
            val = targets[idx][1] < val? targets[idx][1] : val;
            idx++;
        }
        i = idx - 1;
        answer++;
    }
    
    
    return answer;
}