IM

작지만 단단하게

Greedy 기출문제 풀이

회의실 배정

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

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

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

  • 풀이

import java.util.*;

class Meeting implements Comparable<Meeting> {
    int sTime;
    int eTime;
    public Meeting (int sTime, int eTime){
        this.sTime = sTime;
        this.eTime = eTime;
    }

    @Override
    public int compareTo(Meeting o) {
        int result;
        if(eTime - o.eTime>0) result=1;
        else if (eTime == o.eTime) {
            if(sTime - o.sTime>0) result=1;
            else if(sTime - o.sTime<0) result=-1;
            else result=0;
        } else {
            result=-1;
        }

        return result;
    }
}
public class Main {
    static int answer=0, num;

    public void solution(List<Meeting> list) {
        int tmp = 0;
        for(int i=0; i<num; i++){
            if(tmp<=list.get(i).sTime){
                tmp = list.get(i).eTime;
                answer++;
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        num = scan.nextInt();
        List<Meeting> list = new ArrayList<>();
        for(int i=0; i<num; i++){
            int s = scan.nextInt();
            int e = scan.nextInt();
            list.add(new Meeting(s, e));
        }
        Collections.sort(list);

        t.solution(list);
    }
}
  • 정리
    • 우선 입력받은 리스트를 ‘회의가 일찍 끝나는 순서’로 정렬 해야한다. 처음에는 시작시간으로 정렬해보았지만 그렇게하면 시작시간이 빠르고 끝시간이 긴 경우 그 사이의 회의를 하지 못하기에 무조건 빨리 끝나는대로 새 회의를 하는것이 효율적이다
    • 끝시간이 같다면 회의를 빨리 시작하는 순으로 정렬한다. 회의의 시작시간과 끝시간이 같은경우가 있기에 이런경우 일찍시작하는 회의를 마치고 동일타임 회의를 한번 더 하는것이 이득이다.
    • 정렬을 마쳤다면 반복을 돌면서 임시변수(앞회의의 끝시간, 초기세팅 0) 보다 현재 회의의 시작시간이 같거나 이후시간이라면 임시변수의 값을 현재의 회의시작시간으로 바꿔주고
    • 회의 가능시간을 1 증가해준다

Updated: