회의실 배정

 

설명

한 개의 회의실이 있는데 이를 사용하고자 하는 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​

 

문제 해결

 

이 문제를 해결하기 위해서는 가장 빨리 끝나는 회의를 먼저 선택해야 가장 많은 회의실을 선택할 수 있다.

그렇기에 끝나는 시간을 기준으로 오름차순 정렬 후 가능한 회의실을 찾아 카운트해주는 것이 핵심이라고 생각하면 된다.

class Meeting {
    int start;
    int end;

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

 

우선 Meeting 클래스를 만들어준다. 여기에는 회의 시작 시간과 끝나는 시간이 들어간다.

 

List<Meeting> meetings = new ArrayList<>();

for (int i = 0; i < n; i++) {
    int start = in.nextInt();
    int end = in.nextInt();
    meetings.add(new Meeting(start, end));
}

 

위 Meeting 클래스를 저장하는 meetings를 만들어주고 각 회의의 시작 시간과 끝나는 시간을 입력받아 Meeting 객체로 리스트에 저장한다.

 

 

// 회의 끝나는 시간을 기준으로 오름차순 정렬, 끝나는 시간이 같으면 시작 시간으로 정렬
Collections.sort(meetings, (m1, m2) -> {
    if (m1.end == m2.end) {
        return m1.start - m2.start;
    } else {
        return m1.end - m2.end;
    }
});

 

Collections.sort를 사용해 회의 리스트를 끝나는 시간을 기준으로 오름차순 정렬한다. 이 때 끝나는 시간이 같으면 시작 시간으로 정렬해주어야한다. 이 부분을 처음에 놓쳐 몇 테스트는 통과하고 몇 테스트틑 통과하지 못 해 오류가 났다.

int meetingCount = 0;
int lastTime = 0;

for (Meeting meeting : meetings) {
    if (meeting.start >= lastTime) {
        meetingCount++;
        lastTime = meeting.end;
    }
}

System.out.println(meetingCount);

 

정렬된 리스트를 순회하면서, 현재 회의의 시작 시간이 마지막으로 선택된 회의의 끝나는 시간 이후인 경우 해당 회의를 선택해 선택된 회의의 끝나는 시간을 갱신해간다. 최종적으로 가능한 회의 수를 출력해주면 된다.

 

 

 

최종 코드

 

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

public class P02_회의실배정 {

    /** 가장 빨리 끝나는 회의를 먼저 선택해야 제일 많은 회의실 선택 가능함
     *   끝나는 시간 기준으로 오름차순 정렬 후 가능한 회의 찾아서 카운트 **/
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        List<Meeting> meetings = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int start = in.nextInt();
            int end = in.nextInt();
            meetings.add(new Meeting(start, end));
        }

        // 회의 끝나는 시간을 기준으로 오름차순 정렬, 끝나는 시간이 같으면 시작 시간으로 정렬
        Collections.sort(meetings, (m1, m2) -> {
            if (m1.end == m2.end) {
                return m1.start - m2.start;
            } else {
                return m1.end - m2.end;
            }
        });

        int meetingCount = 0;
        int lastTime = 0;

        for (Meeting meeting : meetings) {
            if (meeting.start >= lastTime) {
                meetingCount++;
                lastTime = meeting.end;
            }
        }

        System.out.println(meetingCount);
    }
}

class Meeting {
    int start;
    int end;

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