백준 1931 회의실 배정 Java 풀이

문제

N(1 ≤ N ≤ 100,000) 개의 회의일정 (시작시간, 종료시간) 에 대해서 하나의 회의실에서 가장 많은 회의를 한 개수를 구하려고 한다.

시작시간, 종료시간이 겹쳐서는 안되고 종료시간 이후(+1)에 바로 시작시간이 올 수 있다.

 

접근

정렬만 제대로 되어있다면, 종료시간 이후에 시작시간이 올 수 있는 경우를 세면 자연스럽게 하나의 회의실에서 가장 많이 회의를 하는 경우를 구하게 된다.

 

따라서 핵심 고려사항은 정렬방식이며, 이때 정렬방식은 "종료시간 기준 오름차순" &"종료시간이 동일할 경우 시작시간 기준 오름차순" 이다. 

 

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] meetings = new int[N][2]; // {시작시간, 종료시간}

        // 회의 정보 입력
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            meetings[i][0] = Integer.parseInt(st.nextToken());
            meetings[i][1] = Integer.parseInt(st.nextToken());
        }

        // 끝나는 시간 기준 오름차순 & 끝나는 시간이 같다면 시작 시간 기준 오름차순
        Arrays.sort(meetings, (m1, m2) -> {
            if (m1[1] == m2[1]) {
                return Integer.compare(m1[0], m2[0]);
            }
            return Integer.compare(m1[1], m2[1]);
        });

        int maxMeetings = 0; // 최대 회의 개수
        int lastEndTime = 0; // 마지막으로 선택된 회의의 끝나는 시간

        for (int[] meeting : meetings) {
            // 이전 회의 끝난 후에 시작하는 회의만 선택
            if (meeting[0] >= lastEndTime) {
                maxMeetings++;
                lastEndTime = meeting[1];
            }
        }

        System.out.println(maxMeetings);
    }
}