[Programmers] 요격 시스템

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

프로그래머스

문제 설명

주어진 배열에서 겹치는 구간이 가장 많도록 하는 그리디 문제이다.

풀이 방법

먼저 끝나는 지점을 기준으로 오름차순 정렬한다. 그리고 정렬된 targets 배열을 순회하면서 시작하는 지점이 현재 끝나는 지점보다 크거나 같으면, 즉 겹치는 구간이 끝나면 새로운 구간의 시작이므로 카운트를 추가하고 끝나는 구간을 해당 개구간의 끝나는 지점으로 변경한다.

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        // e 기준으로 오름차순 정렬
        Arrays.sort(targets, (o1, o2) -> {
            return o1[1] == o2[1] ? o1[0] - o2[0] : o1[1] - o2[1];
        });
 
        int end = targets[0][1];
        answer++;
        
        for (int[] t: targets) {
            if(t[0] >= end) {
                end = t[1];
                answer++;
            }
        }
        
        return answer;
    }
}