문제

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

---

입력

• 각 폭격 미사일의 x 좌표 범위 목록 targets

---

출력

• 요격 미사일 수의 최솟값

---

풀이

제한조건

• 1 ≤ targets의 길이 ≤ 500,000
• targets의 각 행은 [s,e] 형태입니다.
  - 이는 한 폭격 미사일의 x 좌표 범위를 나타내며, 개구간 (s, e)에서 요격해야 합니다.
  - 0 ≤ s < e ≤ 100,000,000

접근방법

정렬

예제 입력으로 살펴보자.

입력 : [[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4]]

입력으로는 한 눈에 알기 어렵다.
종료지점을 기준으로 정렬해보자.

정렬 : [10, 14],[11, 13],[5, 12],[4, 8],[3, 7],[4, 5],[1, 4]

정렬을 하고 나면 왼쪽 지점의 경계를 변경시키면서 검사하면 될 것같은 느낌을 받을 수 있다.

이제 하나씩 순회하며 왼쪽의 경계에 주의하며 미사일의 위치를 찾아보자.

• 왼쪽 범위를 더 오른쪽으로 당겨야 하는가?
• 왼쪽 범위가 현재 지점을 포함하는가?

두가지를 중점으로 생각하면 문제를 해결할 수 있다.!

---

코드

import java.util.Arrays;

public class Solution {
		public int solution(int[][] targets) {
		int answer = 0;
		Arrays.sort(targets, (a, b) -> b[1] - a[1]); // x좌표가 클수록 먼저오도록 정렬

		int left = targets[0][0]; // 요격 가능한 가장 오른쪽 지점을 기록
		for (int[] data : targets) {
			if (left < data[1]) {
				left = Math.max(data[0], left); 더 오른쪽에 있는 지점으로 갱신
				continue;
			}
            // 추가적인 미사일 필요
			answer++;
			left = data[0];
		}
		return answer+1;
	}
}