[Coding Test | Programmers] -Interception system (Java)

요격 시스템

Approach

The first approach that came to mind for solving this problem was a greedy algorithm. I attempted to implement it by Merging larger intervals into smaller ones if they are contained within them. But this solution had some problem that couldn't find out a minimum number of interception.

I learned how to solve the problem using the greedy algorithm. The first step in approaching the problem using the greedy algorithm is to sort the data according to certain conditions. Then, you should design it to always make the best decision at each stage.

In this case, we can take advantage of the fact that the start value s of the current interval is the optimal interception point that exceeds the end value e of the previous interval. This position allows for the maximum number of intercepts. (This approach is similar when sorting by the start value s.)

Algorithm & Data Structure

Greedy

Time Complexity

O(n)

Code

import java.util.*;
class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        //sort by the end point (e) in ASC
        Arrays.sort(targets, (a,b) -> Integer.compare(a[1], b[1]));
        
        int interceptionPoint = -1;
        
        for (int[] target : targets){
            if(target[0] >= interceptionPoint){
                answer++;
                interceptionPoint = target[1];
            }
        }
        return answer;
    }
}