[코딩테스트/백준 알고리즘] 1931번 - 회의실 배정 (Java, 자바 풀이)

문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

---

문제 설명

---

문제 풀이

 그리디 알고리즘 문제다. 

 회의 시간표를 회의 시간이 빨리 끝나는 순으로 정렬한다. 만약 끝나는 시간이 같다면 시작 시간 순으로 정렬한다.

회의 종료 시간을 기록하는 end의 초기 값을 0보다 작은 -1로 초기화한다.

정렬된 회의 시간표의 시작 시간을 end와 비교한다.

만약 회의 시작 시간이 end보다 크거나 같으면 count를 증가시키고 end값을 해당 회의의 종료 시각으로 변경한다.

끝까지 수행하여 답을 도출한다.

---

코드

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

class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[][] arr = new int[N][2];
        int count = 0;

        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, (a1, a2) -> a1[1] == a2[1] ? a1[0] - a2[0] : a1[1] - a2[1]);
        
        int end = -1;

	//그리디
        for(int i = 0; i < N; i++) {
            if(arr[i][0] >= end) {
                end = arr[i][1];
                count++;
            }
        }
        
        //출력
        System.out.println(count);
    }
}