[백준 #1931] 회의실 배정

Yujjin·2025년 1월 31일

그리디 알고리즘 백준 정렬 코테

백준

목록 보기

11/20

백준 #1931 회의실 배정

백준 #1931

문제 설명👩‍🏫

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아라.

입출력 예

입력
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

출력
4

-> (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

내 코드💻

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

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

        int n = Integer.parseInt(str);
        int[][] list = new int[n][2];

        StringTokenizer st;
        for(int i=0;i<n;i++){
            str = br.readLine();
            st = new StringTokenizer(str, " ");
            list[i][0] = Integer.parseInt(st.nextToken());
            list[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1]!=o2[1] ? o1[1]-o2[1] : o1[0]-o2[0];
            }
        });

        int finish = 0;
        int answer = 0;

        for(int i=0;i<n;i++){
            if(finish <= list[i][0]){
                finish = list[i][1];
                answer++;
            }
        }
        System.out.println(answer);
    }
}

설명💡

각각의 회의실 종료시간을 기준으로 오름차순으로 정렬한다. (회의가 빨리 끝나야 최대한 많은 회의를 할 수 있기 때문)
처음에는 종료시간을 나타내는 변수인 finish를 0으로 둔다. 그리고 finish와 비교했을 때 시작시간이 그 이후라면 시작한 회의의 종료시간을 다시 finish 변수로 두고 반복한다.