[백준] 온라인 저지 1931번 : 회의실 배정(Java), 그리디

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

 

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

 

 

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

문제 풀이

회의실을 최대한 많이 배정하려면, 끝나는 시간 기준으로 일찍 끝나는 회의부터 진행하면 된다.

= 빨리 끝나는 약속부터 소화하는 것과 같은 원리!

 

회의 시간을 담은 2차원 배열 arr을 끝나는 시간 기준 오름차순 정렬한 후, 먼저 끝나는 회의 부터 count 해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;

public class Main {


    public static void main(String[] args) throws IOException {
        // Scanner sc = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        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, (a, b) -> {
           if(a[1] == b[1]) {
               // 종료 시간이 같으면 시작 시간 기준
               return Integer.compare(a[0], b[0]);
           }
           return Integer.compare(a[1], b[1]);
        });

        int answer = 0;
        int end = -1;

        for(int i=0; i<N; i++) {
            // System.out.println(arr[i][0] + ", " + arr[i][1]);
            int startT = arr[i][0];
            int endT = arr[i][1];

            if(startT >= end) {
                answer++;
                end = endT;
            }
        }
        System.out.println(answer);

    }
}