[백준 - 1931] 회의실 배정 .java

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

문제 분석

1개의 회의실에 회의가 겹치지 않게 최대한 많은 회의 배정

-> 현재 회의의 종료 시간이 빠를수록 정렬

 

But, 종료시간이 같을때는?

-> 시작 시간이 빠른 순으로 정렬

-> 문제 조건 중 시작 시간과 종료 시간이 같을 수도 있다 때문

=> 기준 재정의 해야함

 

2차원 배열이며 시작, 종료시간 2개의 인덱스를 각각 가진다

 

1. 종료 순으로 정렬
2. 현재 회의 시작 시간 >= 이전의 종료 시간: 성공-> 현재 회의 종료시간으로 갱신, 정답 증가

• @Override: Comparator 인터페이스의 compare 메서드를 오버라이드할 때

import java.util.*;

public class Main {
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        // 입력 받아 저장
        int n = sc.nextInt();
        //회의 정보 배열
        int[][] info = new int[n][2];
        for(int i = 0; i < n; i++){
            info[i][0] = sc.nextInt();//시작 시간
            info[i][1] = sc.nextInt();//종료 시간
        }
        //회의 정보를 종료 시간 기준으로 정렬 (종료 시간이 같으면 시작 시간 기준)
        Arrays.sort(info, new Comparator<int[]>() {
            @Override
            public int compare(int[] t1, int[] t2) {
                //종료시간이 같으면 시작시간이 빠른게 우선
                if(t1[1] == t2[1]) return t1[0] - t2[0];
                //종료 시간이 빠른 순서로 정렬
                return t1[1] - t2[1];
            }
        });
        int count = 0;
        int end = -1;//종료 시간
        //정보 배열을 돌면서
        for(int i = 0; i < n; i++){
            //현재 회의 시작시간이 이전 회의 종료 시간보다 크거나 같으면 가능
            if(info[i][0] >= end){
                end = info[i][1]; //현재 회의 종료시간으로 갱신
                count++; //회의 성공이니까 정답 증가
            }
        }
        System.out.println(count);

    }

}

 

 

 

 

추가 - 2025.5.13

import java.util.*;

public class boj{

    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int n=sc.nextInt();

        int[][] table=new int[n][2];
        for(int i=0;i<n;i++){
            table[i][0]=sc.nextInt();//시작시간
            table[i][1]=sc.nextInt();//종료시간
        }
        //종료시간기준 -> 오름차순 정렬
        //종료시간 같으면 시작시간이 빠른게 우선
        Arrays.sort(table, new Comparator<int[]>(){
            public int compare(int[] o1, int[] o2){
                if(o1[1]==o2[1]) return o1[0]-o2[0];//시작이 빠른게 우선
                return o1[1]-o2[1];//종료 오름차순
            }
        });

        int answer = 1;
        int curEnd = table[0][1];//현재 종료된 시간
        for(int i=1;i<n;i++){
            //회의의 시작시간과 끝나는 시간이 같을 수도 있다
            //현재 끝나진 시각과 시작된 시간이 같을 때도 카운트
            if(table[i][0]>=curEnd){
                curEnd=table[i][1];
                answer++;
            }
        }
        System.out.println(answer);
    }

}