회의실 배정

문제 정보

• 백준 골드 5
• 그리디
• 문제 링크

풀이

서로 시간이 겹치지 않는 최대한 많은 회의를 선택하는 문제다.

활동 선택 문제로, 종료 시간을 기준으로 정렬한 다음, 현재 회의의 시작 시간이 이전 회의의 종료 시간 이상인 경우에만 선택하는 방식으로 풀 수 있다.

코드

import java.io.*;
import java.util.*;
 
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());
        int[][] meeting = new int [n][2];
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            meeting[i][0] = Integer.parseInt(st.nextToken());
            meeting[i][1] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(meeting, new Comparator<int[]>(){
            @Override
            public int compare(int[] e1, int[] e2) {
                if (e1[1] == e2[1])
                    return Integer.compare(e1[0], e2[0]);
                return Integer.compare(e1[1], e2[1]);
            }
        });
        
        int answer = 0;
        int lastEnd = 0;
        for (int i = 0; i < n; i++) {
            if (meeting[i][0] >= lastEnd) {
                answer++;
                lastEnd = meeting[i][1];
            }
        }
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        bw.write(answer + "\n");
        bw.flush();
        bw.close();
    }
}

관련 노트

• 활동 선택 문제
• 20260311 ATM