[Java+Python]1931번, 회의실 배정

목차

 

 

Greedy Algorithm

 

[Java+Python]11047번, 동전 0

[Java+Python]11339번, ATM

[Java+Python]1541번, 잃어버린 괄호

[Java+Python]13305번, 주유소

 

문제

 

한 개의 회의실이 있는데 이를 사용하고자 하는 $N$개의 회의에 대하여 회의실 사용표를 만들려고 한다. 

 

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 

 

각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 

 

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 

 

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 

 

이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

 

입력

 

첫째 줄에 회의의 수 $N(1 ≤ N ≤ 100,000)$이 주어진다. 

 

둘째 줄부터 $N+1$ 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 

 

시작 시간과 끝나는 시간은 $2^{31}-1$보다 작거나 같은 자연수 또는 $0$이다.

 

출력

 

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

풀이

 

이 문제를 그리디 알고리즘을 활용해 풀기 위해선 종료 시간을 기준으로 정렬하는 것이 필요하다.

 

첫 회의 종료시간 이후에 시작하면서 종료시간이 가장 빠른 회의를 순서대로 뽑으면 되기 때문이다.

 

추가로 종료 시간이 같을 경우, 시작 시간에 대해 오름차순으로 정렬해 더 빠른 시작 시간을 가진 회의를 골라야 한다.

 

순서에 따라 알고리즘을 정리하면 다음과 같다.

 

1. 입력으로 주어진 회의의 개수 n을 저장하고 이를 바탕으로 회의 정보를 저장할 이차원 배열(리스트) meetings[n][2]를 생성한다.
2. n개의 회의 정보를 위에서 생성한 meetings 배열(리스트)에 저장한다.
3. 회의 종료 시간을 기준으로 배열(리스트)을 오름차순 정렬한다. 종료 시간이 같을 경우 시작 시간을 기준으로 정렬한다.
   이를 통해 그리디 알고리즘을 적용할 수 있다.
4. 회의의 총개수를 저장할 count를 1로 초기화한다. 이는 첫 번째 회의는 반드시 선택하기 때문이다.
5. 마찬가지 이유로 선택된 회의 중 가장 마지막 회의의 종료 시간을 저장할 endTime을 meetings[0][1]로 초기화한다.
6. 반복문을 돌며 시작 시간이 endTime보다 큰 회의가 나오면
   
   
   1. count를 1 증가시켜 준다.
   2. endTime을 해당 회의의 종료 시간으로 갱신한다.
7. 끝까지 순회한 뒤 count를 출력한다.

 

Java

 

package BackJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Prob1931 {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());

		int[][] meetings = new int[n][2];

		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			meetings[i][0] = Integer.parseInt(st.nextToken());
			meetings[i][1] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(meetings, Comparator.comparingInt((int[] value) -> value[1]).thenComparingInt(value -> value[0]));

		int count = 1;
		int endTime = meetings[0][1];

		for (int i = 1; i < n; i++) {
			if (meetings[i][0] >= endTime) {
				count++;
				endTime = meetings[i][1];
			}
		}

		System.out.println(count);
	}
}

 

Python

 

import sys

n = int(sys.stdin.readline().rstrip())
lst = []

for i in range(n):
    lst.append(list(map(int, sys.stdin.readline().rstrip().split())))

lst = sorted(lst, key=lambda x: (x[1], x[0]))

cnt = 1
end_time = lst[0][1]

for i in range(1, n):
    if lst[i][0] >= end_time:
        cnt += 1
        end_time = lst[i][1]

print(cnt)

 

Performance