[백준] Greedy: 회의실 배정

문제

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

입력

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

 

출력

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

 

문제 접근

• 회의실을 최대한 이용하도록 회의실을 배정해야 함.
• 많은 회의가 진행되기 위해서는 최대한  앞의 회의가 빨리 끝나야 한다. --> Greedy
• 즉 회의가 끝나는 순으로 정렬이 필요하다.
• 만약 종료시간이 같은 경우는 어떻게?????
• 종료시간이 같은 경우 시작시간을 오름차순으로 정렬해 주어야 한다.
• 예를들어 (4 , 6), (6 , 6) 와 같은 두 회의가 있다고 하자.
• (4, 6), (6, 6)으로 정렬한 경우는 (4, 6)종료 후 (6, 6)진행이 가능하다.
• 하지만 (6, 6) , (4, 6)으로 정렬하면 (6, 6)진행 후 (4, 6)진행이 불가능하다.
• 따라서 오름차순으로 정렬해야 시작&종료가 같은 회의를 cnt에 반영이 가능하다.

package baekjun;

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

public class _1931 {


    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++){
            String[] info = br.readLine().split(" ");
            meetings[i][0] = Integer.parseInt(info[0]);
            meetings[i][1] = Integer.parseInt(info[1]);
        }

        //정렬, 회의종료시간 오름차순
        Arrays.sort(meetings, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]){
                    return o1[1] - o2[1];
                }else{ //종료 시간이 같은 경우 시작시작 오름차순
                    return o1[0] - o2[0];
                }
            }
        });

        //판단
        int end = 0;
        int count=0;
        for (int i=0; i<N; i++){
            int[] current = meetings[i];

            //현 회의 시작이 앞 종료시간보다 늦은지.
            if (current[0] >= end){
                count++;
                end = current[1];
            }
        }

        System.out.println(count);

    }
}