[Silver 2] [Java] 회의실 배정 (1931번)

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

문제 풀이

회의실의 끝나는 시간을 기준으로 오름차순 정렬을 통해 바로 참석할 수 있는 회의실 시작시간을 찾아냈습니다.

끝나는 시간만 정렬을 할 경우 80%정도 까지만 정답이 올라가고 실패하는 경우가 생겼는데 끝나는 시간이 같을 경우, 회의실 시작 시간 또한 비교를 해줘야 합니다. 끝나는 시간이 같을 경우, 시작시간이 좀 더 빠른 회의실을 오름차순으로 모든 객체를 정렬시켜줍니다.

 

Java Code

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


class MeetingRoom implements Comparable<MeetingRoom> {
    int startTime, endTime;

    public MeetingRoom(int startTime, int endTime) {
        this.startTime = startTime;
        this.endTime = endTime;
    }

    @Override
    public int compareTo(MeetingRoom o) {
        // 현재 끝나는 시간보다 다음 인덱스의 끝나는 시간이 더 작을 경우 순서 변경 (양수를 반환해야 배열순서가 바뀐다)
        if (this.endTime > o.endTime) {
            return 1;
        }
        // 끝나는 시간이 같은 경우 시작 시간도 비교해줘야 한다.
        else if (this.endTime == o.endTime) {
            // 시작 시간이 다음 인덱스의 시작시간이 더 작을 경우 순서 변경
            if (this.startTime > o.startTime) {
                return 1;
            } else {
                return -1;
            }
        } else {
            return -1;
        }
    }
}

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        MeetingRoom[] meetingRooms = new MeetingRoom[N];

        for (int count = 0; count < N; count++) {
            String[] input = reader.readLine().split(" ");
            meetingRooms[count] = new MeetingRoom(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
        }

        Arrays.sort(meetingRooms);

        int answer = 0;
        int startTime = 0;

        for (int index = 0; index < meetingRooms.length; index++) {
            if (startTime <= meetingRooms[index].startTime) {
                startTime = meetingRooms[index].endTime;
                answer++;
            }
        }

        System.out.println(answer);
    }
}