[Greedy Algorithm] 회의실 배정

 

 

 

설명

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

 

 

입력

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데
이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 회의시간은 0시부터 시작한다.
회의의 시작시간과 끝나는 시간의 조건은 (시작시간 <= 끝나는 시간)입니다.

 

 

출력

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

 

 

예시 입력1

5
1 4
2 3
3 5
4 6
5 7

 

 

예시 출력1

3

 

 

예시 입력2

3
3 3
1 3
2 3

 

 

예시 출력2

2

 

 

 

풀이

핵심 로직은 다음과 같다.

회의 종료 시간을 기준으로 오름차순 정렬을 한다. 회의가 빨리 끝날 수록 최대 가능한 회의의 수가 많아진다.

다음 회의의 시작 시간이 이전 회의 종료 시간보다 크거나 같으면 회의 수를 1 증가시킨다.

 

예시1에 대한 설명을 그림으로 나타낸 것이다.

 

 

주의사항은 다음과 같다.

끝나는 시간이 모두 같은 경우가 존재할 수 있다. (예시2) 이럴 경우에는, 시작 시간에 대해서도 오름차순 정렬을 해야한다.

회의 시작 시간을 오름차순으로 정렬한다면 최선의 선택이 될 수 없음을 생각하여 회의 종료 시간을 기준으로 오름차순 정렬을 한다.

 

 

 

코드

package inflearn._9_2;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

class Time implements Comparable<Time> {

    public int start, end;

    public Time(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Time o) {
        if(this.end == o.end) return this.start - o.start; // 끝나는 시간이 같다면 시작 시간으로 오름차순 정렬
        else return this.end - o.end; // 끝나는 시간이 다르다면 종료 시간으로 오름차순 정렬
    }
}

public class Main {

    public static int solution(ArrayList<Time> arr, int n) {

        int cnt = 0;

        Collections.sort(arr); // 정렬

        int endTime = 0; // 회의가 끝나는 시간, 초기값은 0

        for(Time ob : arr) {
            if(ob.start >= endTime) {
                cnt++;
                endTime = ob.end;
            }
        }

        return cnt;

    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        ArrayList<Time> arr = new ArrayList<>();

        for(int i = 0; i < n; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            arr.add(new Time(start, end));

        }

        sb.append(solution(arr, n));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}