[Algorithm] 회의실 배정(Greedy, 그리디)

설명

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

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

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

 

입력

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데

이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.

회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

 

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

 

예시 입력 / 출력

5 1 4 2 3 3 5 4 6 5 7	3
3 3 3 1 3 2 3	2

 

풀이 과정.

이 문제는 입력 받은 회의를 compareTo함수를 오버라이드하여 정렬만 잘 해주면 엄청 쉽게 풀 수 있다.

1. 우선 끝나는 시간 기준으로 정렬 해준다.

2. 끝나는 시간이 같을 경우는 시작 시간 기준으로 정렬 해준다.

3. 정렬된 값들을 가지고 최대의 사용 회의 수를 구한다.

 

 

풀이.

// 회의의 시간대를 객체로 저장하기위한 클래스를 하나 만든다.
// 회의의 정렬을 위해 Comparable의 compareTo를 오버라이드하여 사용한다.
class Time implements Comparable<Time>{
    int st;
    int et;
    public Time(int st, int et){
        this.st = st;
        this.et = et;
    }
    @Override
    public int compareTo(Time t) {
        if(this.et == t.et){
            return this.st - t.st;
        }else{
            return this.et - t.et;
        }
    }
}

public class Main{
    static int n;
    static int sum = 0;
    static ArrayList<Time> timeArr = new ArrayList<>();
    static void Solution(){
        int temp = 0;
        for(Time t : timeArr){
            if(temp <= t.st){
                temp = t.et;
                sum++;
            }
        }
        System.out.println(sum);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            timeArr.add(new Time(a, b));
        }
        Collections.sort(timeArr);
        Solution();
    }
}

 

---

 

정리 :

시작 시간이 아니 끝나는 시간을 확인한다.

회의가 빨리 끝나는 것부터 처리해야 최상의 결과가 나온다.