[Java] 백준 1931번 - 회의실 배정

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

1931번: 회의실 배정

[문제]

 

 

[풀이]

 

처음엔 "시작시간"기준으로 정렬후, 가능한 모든 회의 조합을 구하여 max값을 뽑아내려 했으나, 시간초과가 나왔습니다.

따라서 질문하기의 도움을 받아 "종료시간"기준으로 정렬하여 푸는 문제라는 힌트를 얻었습니다.

 

- Compatable<>을 이용하여 종료시간으로 정렬하며, **만약 종료시간이 같다면 start시간이 짧은순서대로 정렬

1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

 

(1,4) -> time: 4 이므로 4보다 시작시간중 크거나 같은값이 나오면 갱신 -> (5,7) -> (8,11) -> (12,14) 

 

** end 시간이 같은 경우를 고려하지 못해 88%에서 틀려서 질문하기에 올라온 반례를 통해 발견하였습니다.

반례
5
6 7
6 6
5 6
5 5
7 7

정답 : 5
출력 : 4

 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Room implements Comparable<Room>{
    int start;
    int end;

    public Room(int start, int end) {
        this.start = start;
        this.end = end;
    }
    @Override
    public int compareTo(Room o) {
        if(this.end == o.end) {
            return this.start - o.start;
        }
        return this.end - o.end;
    }
}
public class Main {
    public static int N;
    public static Room[] room;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        room = new Room[N];
        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] = new Room(start, end);
        }
        Arrays.sort(room);
        countRoom();
    }

    // cnt : 진행된 회의 총합
    public static void countRoom() {
        // 시작은 무저건 0 부터임
        int time = room[0].end;
        int cnt = 1;
        for(int i=1;i<N;i++) {
            if(time <= room[i].start) {
                time = room[i].end;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}