백준 1931번 회의실 배정 자바 풀이

❓문제

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

---

🔠 입력

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

 

---

🖨️출력

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

---

✍️ 예제 입력

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

✔️ 예제 출력

4

 

 

---

💡해설

회의시간을 정렬하는 경우를 생각해본다.

시작시간을 기준으로 할 경우 반례가 있을 수 있다.

(1 - 13, 2 - 3, 3, 6)

 

종료시간을 기준으로 선택하면 회의실 시간을 효율적으로 선택할 수 있다.

다음 회의는 이전 회의의 종료시간보다 큰 시작시간을 고른다.

 

 

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

public class Main {
    

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int count = Integer.parseInt(br.readLine());
        int[][] meetingTimes = new int[count][2];

        for(int i = 0; i < count; i++) {
            String times = br.readLine();
            meetingTimes[i][0] = Integer.parseInt(times.split(" ")[0]);
            meetingTimes[i][1] = Integer.parseInt(times.split(" ")[1]);
        }


        Arrays.sort(meetingTimes, (o1, o2) -> {
            // 종료 시간 오름차순, 시작시간 오름차순
            return o1[1] != o2[1] ? o1[1] - o2[1] : o1[0] - o2[0] ;
        });

        
        int t = 0;
        int answer = 0;
        
        for(int i = 0; i < meetingTimes.length; i++) {
            int[] arr = meetingTimes[i];
            System.out.println(arr[0] + ", " + arr[1]);

            if(t <= arr[0]) {
                answer+=1;
                t = arr[1];
            }
        }

        System.out.println(answer);
    }

}