[Java] 백준 1931번 - 그리디 알고리즘

import java.util.*;
import java.io.*;

public class s2_1931 {
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] time = new int[N][2];
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i][0] = Integer.parseInt(st.nextToken());
            time[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(time, (o1, o2) -> { 
            if(o1[0] == o2[0]){ 
                return Integer.compare(o1[1],o2[1]);
            }
            else{ 
                return Integer.compare(o1[0],o2[0]); 
            } 
        });
        // 회의 시작 시간 순서대로 이중 배열을 정렬
        // 시작이 같으면 끝나는 시간으로 정렬 -> (1,5),(1,1) 순서면 카운트 안되기 때문

        int cnt = 0;
        int end = -1;

        for (int i = 0; i < N; i++){
            if (end == -1){
                end = time[i][1];
            }
            else if (end <= time[i][0]){
                cnt++;
                end = -1;
                i--;
            }
            else{
                end = Math.min(end, time[i][1]);
            }
        }
        // 회의가 최대한 일찍 끝나는 시간(end)에 대한 그리디 알고리즘
        // 시작 시간, 끝나는 시간 모두 end보다 적으면 end를 변경
        if (end != -1) cnt++;
        System.out.println(cnt);
    }
}