[프로그래머스 2레벨] 요격 시스템 (C++)

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

using namespace std;

int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(), targets.end());
    
    int i = 0;
    while (i < targets.size()) 
    {
        int end = targets[i][1];
        answer++;
        i++;
        
        while (i < targets.size() && targets[i][0] < end) 
        {
            end = min(end, targets[i][1]);
            i++;
        }
    }
    
    return answer;
}

 

최소값을 찾기 위해 가장 많이 겹치는 구간을 찾아야 한다.

따라서 우선 오름차순 정렬을 해주고, end 값을 기준으로 값을 체크할 필요가 있다.

 

현재 end 값을 기준으로, 다음 값의 start 값을 체크한다.

만약 start가 end보다 작다면, 두 값은 겹치는 범위에 해당하므로 추가 미사일이 필요 없을 것이다.

해당 start의 end 값이 직전 end 값보다 작다면 end 값을 새로 갱신하여 가장 좁은 공통 구간을 유지시킨다.

이를 반복하며 겹치는 구간 만큼 인덱스인 i 값을 증가시켜 범위를 정해준다.

 

이를 반복하며 모든 [s, e] 구간을 체크해 가능한 가장 좁은 공통 구간의 개수를 카운팅하게 된다.