[BOJ/Java] 1931. 회의실 배정

[BOJ/Java] 1931. 회의실 배정

 

1931번: 회의실 배정

---

문제 해석

이 문제는 회의실 한 개를 사용할 때 주어진 회의 목록 중에서 최대한 많은 회의를 배정하는 문제이다. 각 회의는 시작 시간과 종료 시간이 주어지며, 회의는 종료 시간과 동시에 다른 회의가 시작될 수 있다. 주어진 회의를 최적으로 배정해야 하며, 회의의 최대 개수를 반환해야 한다.

풀이 과정

제출된 Java 코드는 우선순위 큐(PriorityQueue)를 사용하여 회의를 종료 시간에 따라 정렬하고, 회의가 동일한 종료 시간을 가지면 시작 시간에 따라 정렬한다. 이러한 정렬은 각 회의를 최대한 겹치지 않게 배정하기 위해 사용된다.

 

• 데이터 입력 및 우선순위 큐 초기화: 입력을 받고 각 회의를 우선순위 큐에 추가한다. 큐는 회의를 종료 시간이 빠른 순서로 정렬한다.
• 회의 배정 솔루션 (sol 메소드): 초기에 가장 먼저 끝나는 회의를 선택하고, 다음으로 선택할 수 있는 회의 중 가장 빨리 끝나는 회의를 선택한다. 이는 다음 회의의 시작 시간이 현재 회의의 종료 시간보다 같거나 늦어야 선택할 수 있다는 조건으로 진행된다.

코드

package edu.ssafy.im.BOJ.Silver.S1.No1931;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		new Main().io();
	}

	Queue<Time> pq; // 회의를 저장할 우선순위 큐

	private void io() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine()); // 회의의 수
		pq = new PriorityQueue<>((o1, o2) -> {
			if(o1.end == o2.end) {
				return o1.start - o2.start; // 종료 시간이 같다면 시작 시간이 빠른 순으로 정렬
			}
			return o1.end - o2.end; // 종료 시간이 빠른 순으로 정렬
			});
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			pq.offer(new Time(start, end)); // 회의 시간을 큐에 추가
		}
		
		sb.append(sol()); // 최대 회의 수 계산
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private int sol() {
		int ans = 1; // 최소 한 개의 회의는 진행
		int end = pq.poll().end; // 가장 빨리 끝나는 회의 선택
		while(!pq.isEmpty()) {
			if (end <= pq.peek().start) { // 다음 회의 시작 시간이 현재 회의 종료 시간 이후라면
				ans++;
				end = pq.poll().end; // 해당 회의를 선택
			} else {
				pq.poll(); // 겹치는 회의는 제거
			}
		}
		return ans;
	}

	class Time {
		int start, end;

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

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 주로 우선순위 큐의 연산에 의존한다. 우선순위 큐의 삽입 및 삭제 연산은 로그 시간 복잡도(O(logn))를 가지므로, 전체 시간 복잡도는 O(nlogn)이 된다.

느낀점

이 문제는 우선순위 큐를 효과적으로 사용하여 간단하고 효율적인 방식으로 해결할 수 있었다. 종료 시간을 기준으로 회의를 정렬하고, 가능한 많은 회의를 스케줄링하는 전략은 다양한 최적화 문제에 적용할 수 있는 유용한 접근 방식이다.