[백준] 1931번: 회의실 배정

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

 

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

 

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.

 

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

---

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Baek1931 {
    public static class meet implements Comparable<meet> {
        int startTime;
        int endTime;

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

        @Override
        public int compareTo(meet o) {
            if(endTime - o.endTime == 0) {
                return startTime - o.startTime;
            }
            return endTime - o.endTime;
        }
    }

    public static meet[] meets;
    static ArrayList<meet> selectMeet;
    public static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        meets = new meet[n];


        for(int i = 0; i < n; i++) {
            meets[i] = new meet(scanner.nextInt(), scanner.nextInt());
        }

        Arrays.sort(meets);

        int count = 0;
        int max = 0;

        selectMeet = new ArrayList<>();
        selectMeet.add(new meet(0, 0));

        for (meet meet : meets) {
            if (selectMeet.get(selectMeet.size() - 1).endTime <= meet.startTime) {
                selectMeet.add(meet);
            }

            count = selectMeet.size() - 1;

            if (count > max) {
                max = count;
            }
        }

        System.out.println(max);
    }


}

 

 객체를 이용하였고 Comparable 인터페이스의 CompareTo를 사용하여 끝나는 시간 기준으로 오름차순 정렬을 하였다.

 

끝나는 시간 기준으로 오름차순 정렬을 한 이유는 최대한 많은 회의를 하려면 빨리 끝나는 회의들을 배정해야 하기 때문이다.