[백준] CLASS3 1931 회의실 배정 - JAVA [자바]

안녕하세요. 이번에는 백준 1931 회의실 배정 문제를 풀어보려고 합니다.

 

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

1931번: 회의실 배정

---

Problem

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

 

사진 1. 문제

---

Solution

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[][] room =  new int[N][2];
        
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            
            room[i][0] = start;
            room[i][1] = end;
        }
        
        // 회의 시간이 끝나는 시간이 빠른 순으로 정렬
        Arrays.sort(room, (a1, b1) -> {
            if(a1[1] == b1[1]) {
                return a1[0] - b1[0];
            } else {
                return a1[1] - b1[1];
            }
        });
        
        int count = 0;
        int endTime = 0;
       
        for(int i = 0; i < N; i++) {
            if(endTime <= room[i][0]) {
                count++;
                endTime = room[i][1];
            }    
        }
        
        System.out.println(count);
    }
}

 이번 문제는 회의가 겹치지 않으면서 회의를 가장 많이 하는 횟수를 구하는 문제이다. 회의를 가장 많이 한다는 것은 회의 시간이 짧으면서 회의 시간 공백이 작은 것을 구하면 된다. 그래서 Comparator를 사용하여 회의 마감이 빠른 순으로 정렬하면서 회의 마감 시간이 같으면 회의 시작 시간이 빠른 순으로 정렬시키는 방식으로 접근하면 된다.

 

핵심 코드

	// 회의 시간이 끝나는 시간이 빠른 순으로 정렬
	Arrays.sort(room, (a1, b1) -> {
		if(a1[1] == b1[1]) {
			return a1[0] - b1[0];
		} else {
			return a1[1] - b1[1];
        }
	});
        
    int count = 0;
    int endTime = 0;
     
    // 회의의 수를 세는 코드 
    for(int i = 0; i < N; i++) {
		if(endTime <= room[i][0]) {
			count++;
			endTime = room[i][1];
		}    
	}

---

Performance

사진 2. 실행 결과