백준 1931 회의실배정 Java

회의실을 겹치지 않게 사용하면서 최대한 회의를 많이 할 수 있는 횟수를 출력하는 문제이다.

입력에는 회의 수와 회의 시작시간과 끝나는 시간이 주어지는데

끝나는 시간과 시작하는 시간이 겹쳐도 시작할 수 있고 

시작하는 시간과 끝나는시간이 같은 경우엔 시작과 동시에 끝난다고 생각한다.

 

가장 많이 회의의 수를 찾으려면

회의가 끝나는 순으로 정렬하면 된다.

풀이법을 들으면 정말 쉬워보인다. 하지만 생각해내기는 굉장히 어렵다..

 

회의가 끝나는 순으로 정렬하고 첫 번째 회의부터 끝나는 시간과

시작 시간이 같거나 큰수로 회의의 수를 카운트하면 된다.

주의해야 할점은 끝나는 시간 순으로 정렬할 때

시작 시간도 같이 정렬해줘야 한다는 점이다.

 

4

1 1 

2 2

1 1

1 2

 

와 같이 입력이 주어 졌을 때 끝나는 시간만으로 정렬하면

1 1

1 1

2 2

1 2

와 같이 정렬이 돼서 최대 회의 수가 4번이아닌 3번이 되게된다.

 

그러므로 시작시간까지 같이 정렬한다. 항상 정렬 조건을 적을 때

문제와 상관이 없다는 생각이 들어도 주어진 필드를 전부 정렬하는

습관을 가져야 겠다.

 

암튼 주의할 점과 끝나는 시간순으로 정렬해야 한다는 것만 알면 정답률 29퍼센트의 문제가

정말 쉬운 문제가 되어버린다.

 

import java.util.Arrays;
import java.util.Scanner;
 
public class Q1931 {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Conference [] arr = new Conference[n];
        
        for(int i=0; i<n; i++)
            arr[i] = new Conference(scan.nextInt(), scan.nextInt());
        
        Arrays.sort(arr);
        
        int cnt = 1;
        int end = arr[0].end;
        for(int i=1; i<n; i++) {
            if(arr[i].start>=end) {
                cnt++;
                end = arr[i].end;
            }
        }
        
        System.out.println(cnt);
    
    }
 
}
class Conference implements Comparable<Conference> {
    int start;
    int end;
    
    public Conference(int start, int end) {
        this.start = start;
        this.end = end;
    }
 
    @Override
    public int compareTo(Conference o) {
        int r = this.end - o.end;
        if(r==0)
            r = this.start - o.start;
        return r;
    }