bj_1931.md

1931. 회의실 배정

Summary

🙇‍♂️ URL : https://www.acmicpc.net/problem/1931
🤷‍♂️ Difficulty: ?
💆‍♂️ Submissions : Success

Source code

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Comparator;
 
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
 
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
      
      	// 결과 값을 담기 위한 변수
      	int result = 0;
      
      	// 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 
        int N = sc.nextInt();
      	
        // 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데,
      	// 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 
        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            arr[i][0] = sc.nextInt();	// i번째 회의의 시작시간
            arr[i][1] = sc.nextInt(); // i번째 회의의 종료시간
        }
      
      	// 끝나는 시간이 빠르다 = 다음 회의가 더 빠르게 시작할 수 있다
       	// 종료 시간([i][1])에 따라 주어진 배열을 정렬
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] curr, int[] next) {
              	// 서로 다른 두 회의의 시간을 비교해야 함 -> curr, next
                // curr[0], next[0] 배열 -> arr[i][0](두 회의의 시작 시간)
                // curr[1], next[1] 배열 -> arr[i][1](두 회의의 종료 시간)

              	if(curr[1] == next[1]){
                    // 종료 시간이 같은 값이 존재하면, 시작시간에 따라 다시 정렬
                    return Integer.compare(begin[0], end[0]);
                }
              
                // 두 회의의 종료시간이 다르면, 종료 시간에 따라 정렬
                return Integer.compare(curr[1], next[1]);
            }
        });
 
        // 다음 회의의 시작 시간과 비교
        int isFinished = -1;    
      
        for (int i = 0; i < N; i++) {
            // 현재 차례 회의의 시작시간이 이전 회의의 종료시간보다 늦을 경우 -> 회의 가능
            if (arr[i][0] >= isFinished) {
              	// 현재 회의의 종료시간을 다음 회의의 시작시간과 비교하기 위해 저장 
                isFinished = arr[i][1];    
                result++;
            }
        }
        System.out.println(result);
    }
}

How to Approach

위의 주석에 대부분의 설명을 대신한다.

먼저 주어진 회의를 시간 순서에 맞게 정렬한다. 정렬 기준은 종료 시간이 빠른 순서이나, 만약 두 비교 대상의 종료 시간이 같다면 시작 시간이 빠른 순서대로 정렬한다. 정렬 이후에는 현재의 종료시간과 다음 회의의 시작 시간을 비교하면서 갯수를 추가한다.