[Java] 회의실 배정

문제

 

주의할 점

그리디 알고리즘 문제이다. 그리디 알고리즘은 매 선택에서 현재 당장 최적인 답을 선택한다. 이 문제는 매 선택에서 회의실 끝나는 시간이 빠른 회의를 선택한다는 점에서 그리디 알고리즘이라고 할 수 있다.

 

시작 시간과 끝나는 시간을 묶어서 하나의 객체를 만들기 위해 Meeting 클래스를 선언하고 

객체를 비교하기 위해 Comparable 인터페이스를 구현하였다. Comparable 인터페이스는 반드시 compare 메소드를 구현해야한다. 그리고 이 메소드를 구현함으로써 객체를 비교할 수 있다.

 

코드

package 인프런.그리디.회의실배정.방법1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Meeting implements Comparable<Meeting> {
    int start;
    int end;

    public Meeting(int start, int end) {    // 객체를 생성할 때 인스턴스 변수값 설정
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Meeting o) {
        if (this.end == o.end)  // 종료 시간이 같다면 
            return this.start - o.start;    // 시작 시간으로 정렬
        else    // 종료시간이 다르면 종료 시간으로 정렬
            return this.end - o.end;
    }
}

public class Main {
    public int solution(int n, ArrayList<Meeting> list) {
        int answer=0;

        Collections.sort(list); // 정렬
        
        int endMeeting = 0; // 초기 설정
        for (Meeting Meeting : list) {
            if (endMeeting <= Meeting.start) {  // 전 회의 끝날시간보다 현재 미팅 시작이 크거나 같다면
                answer++;
                endMeeting = Meeting.end;
            }
        }
        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList<Meeting> list = new ArrayList<>();
        for (int i=0; i<n; i++) {
            int start = in.nextInt();
            int end = in.nextInt();
            list.add(new Meeting(start, end));
        }
        System.out.println(T.solution(n, list));
    }
}