[JUNGOL] 1828 냉장고

문제

N개의 화학 물질 C1, C2, …, Cn이 있다.
이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다.
즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다.

이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다.
이를 해결하는 프로그램을 작성하시오.

입력형식

첫줄에 화학물질의 수 N이 입력된다. N의 범위는 1이상 100 이하이다.
두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다.
보관온도는 -270° ~ 10000°이며, 각 냉장고는 임의의 정해진 온도를 일정하게 유지할 수 있고, 냉장고는 아주 크다고 가정한다.

출력형식

첫줄에 최소로 필요한 냉장고의 대수를 출력한다.

입력 예

4
-15 5
-10 36
10 73
27 44

출력 예

2

---

풀이

1도라도 겹치는 온도가 있다면 냉장고를 같이 사용할 수 있다. 전혀 겹치지 않을 때 새로운 냉장고가 필요하게 된다.

겹치지 않는 경우는 이전까지 가지고 있던 물질 중 가장 온도가 높은 최고 온도보다 현재 물질의 최저 온도가 더 높을 때다.

그래서 우선 최고온도 순으로 오름차순 정렬을 해준 뒤, 정렬된 물질을 하나씩 순서대로 보면서 최고온도와 현재의 최저온도를 비교한다.

현재 최저온도가 더 높다면 겹치지 않으므로 냉장고 개수를 증가시킨다.
또한 최고온도도 현재의 최고온도로 바꿔준다.

마지막으로 냉장고의 개수를 반환하면 된다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
  
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
  
        // base case
        if (n == 1) {
            System.out.println(1);
            return;
        }
  
        StringTokenizer st;
        int[][] arr = new int[n][2];
  
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
  
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });
  
        int result = 1;
        int maxDegree = arr[0][1];
  
        for (int i = 1; i < n; i++) {
            if (maxDegree < arr[i][0]) {
                maxDegree = arr[i][1];
                result++;
            }
        }
  
        System.out.println(result);
    }
}