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

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

프로그래머스

 

[문제 요약]

• (s, e)구간의 x축에 평행하는 직선들의 집합에서 모든 선을 관통하기 위한 y축에 평행하는 직선의 최소 개수를 찾는 문제.

 

[풀이]

• Greedy하게 풀리는 문제 O(NlogN)에 풀린다.
• e 값을 기준으로 오름차순으로 정렬한 이후, e 보다 크거나 같은 s 값이 나올 때 마다 새로운 선이 필요하다.
  (e 값을 기준으로 정렬했기 때문에 n번째의 s 값이 n - k번째의 e 값보다 크다면 같은 범위에 속하지 않음이 자명하다.)

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

using namespace std;

int solution(vector<vector<int>> targets) {
	int answer = 0;

	sort(targets.begin(), targets.end(), [&](vector<int> &v1, vector<int> &v2) {
		return v1[1] < v2[1];
	});

	int minVal = -1;
	
	for (int i = 0; i < targets.size(); i++) {
		int s = targets[i][0];
		int e = targets[i][1];
		
		if (minVal <= s) {
			answer++;
			minVal = e;
		}
	}

	return answer;
}