단속 카메라(프로그래머스, Java)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42884

코딩테스트 연습 - 단속카메라 | 프로그래머스

알고리즘 설명:

들어오는 시간과 나가는 시간 두 값을 가진 배열들에 대해서 두 시간의 사이 값들 중 겹치는 시간이 있는 배열들의 집합 수를 최소한으로 하는 집합 방법을 찾는 문제이다.

• 나가는 시간을 기준으로 정렬을 한다.

• 처음 들어온 배열의 나간 시간을 기준으로 설정하고 기준보다 빨리 들어온 시간을 가진 배열들을 하나의 집합이라고 생각한다.

• 들어온 시간이 기준을 벗어난다면 벗어난 배열의 나간 시간을 기준으로 재설정

• 기준이 바뀌는 상황을 count 하면 최소한의 집합 개수이다.

막혔던 지점:

처음에는 들어온 시간을 기준으로 정렬을 했더니 예외상황이 많아 코드가 복잡해졌다.

package test;

import java.util.Arrays;
import java.util.Comparator;

public class RaidCamera {
	public static int solution(int[][] routes) {
		int answer = 0;
        Arrays.sort(routes, new Comparator<int []>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				
				return o1[1] - o2[1];
			}
		});
        int min = Integer.MIN_VALUE;
        for(int[] route: routes) {
        	if(min<route[0]) {
        		answer++;
        		min = route[1];
        	}
        }
        
        
        return answer;
    }
	public static void main(String[] args) {
		int[][] routes = {{-20,15}, {-14,-5}, {-18,-13}, {-5,-3}};
		System.out.println(solution(routes));

	}

}