백준 1931번 - 회의실 배정

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

1931번: 회의실 배정

 

---

위 문제는 최대한 진행할 수 있는 회의의 수를 출력하는 문제인데 회의 시간이 겹치지 않도록 해야한다.

 

 

예를 들어

1 4

5 7

 

이런 식으로 한 시간 차이로 진행할 수 있으며

 

 

1 4

4 4 

4 5

 

이런 식으로 회의 시작 시간과 종료 시간이 같은 경우에도 가능하며 이 경우 출력은 3이 된다.

 

 

 

 

※위 문제 핵심

 

1. 종료시간을 기준으로 오름차순 정렬한다.

 

2. 종료시간이 같고 시작 시간이 다른 경우는 또 시작시간을 기준으로 오름차순 해야한다.

 

 

 

▶코드

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));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int arr[][] = new int[N][2];
        int cnt = 0;
        int time = 0;

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });

        for(int i=0;i<N;i++){
            if(time <= arr[i][0]){
                time = arr[i][1];
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

 

 

위 코드에서 다음 정렬 부분은 기본적으로 종료 시간을 기준으로 오름차순 정렬하되

종료 시간이 같은 경우 ( o1[1] == o2[1] ) 는 시작 시간을 기준으로 오름차순 정렬 ( o1[0] - o2[0] ) 한다는 의미이다.

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