문제
하나의 회의실을 사용하려는 N개의 회의가 있을 때, 각 회의는 시작 시간과 끝 시간이 주어진다. 겹치지 않게 회의를 배정할 때 최대한 많은 회의를 배정할 수 있는 수를 구하는 문제다. (회의가 끝나는 동시에 다른 회의를 시작할 수 있다.)
입력
- 첫째 줄: 회의 수 N (1 이상 100,000 이하)
- 둘째 줄부터 N개 줄: 회의의 시작 시간, 끝 시간 (0 이상 2^31 - 1 이하의 정수)
출력
최대로 배정할 수 있는 회의의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 | 4 |
풀이
종료 시간이 빠른 순으로 정렬하고, 종료 시간이 같으면 시작 시간이 빠른 순으로 정렬한 뒤 그리디하게 회의를 선택한다.
- 회의 배열을 종료 시간 오름차순, 종료 시간이 같으면 시작 시간 오름차순으로 정렬한다.
- 현재 시간
time = 0, 선택 횟수cnt = 0으로 초기화한다. - 정렬된 순서대로 회의를 순회하며,
time <= 시작 시간인 회의를 선택한다. - 선택하면
time = 해당 회의 종료 시간,cnt++을 수행한다. - 최종
cnt를 출력한다.
핵심 아이디어: 가장 일찍 끝나는 회의를 우선 선택하면 이후에 배정 가능한 회의의 수를 최대화할 수 있다. 종료 시간이 같을 때 시작 시간으로 정렬하는 이유는 회의 시작과 끝이 동일한 경우(시작 = 끝)도 유효하기 때문이다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Day04BOJ1931회의실배정 { // 1931 회의실 배정
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1])
return o1[0] - o2[0];
return o1[1] - o2[1];
}
}); // 정렬에서 계속 시간초과... 백준은 C로 풀어야 하는 문제가 많음.
int cnt = 0;
int time = 0;
for (int i = 0; i < N; i++) {
if (time <= arr[i][0]) {
time = arr[i][1];
cnt++;
}
}
// for (int[] a : arr)
// System.out.println(Arrays.toString(a));
System.out.println(cnt);
br.close();
}
}복잡도
- 시간: O(N log N) — 정렬, 이후 순회는 O(N)
- 공간: O(N) — 회의 배열