[java]백준 1931번: 회의실 배정, 그리디 알고리즘

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

코드

import java.io.*;
import java.util.*;

public class j1931 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Meeting> meeting = new PriorityQueue<>();
		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());

			meeting.add(new Meeting(start, end));
		}
		int cnt = 1;
		Meeting m = meeting.poll();

		int e = m.end;

		while (!meeting.isEmpty()) {
			m = meeting.poll();
			if (e <= m.start) { //현재 끝나는 시간이 살펴볼 수업의 시작 시간보다 더 일찍이면 수업 듣는다.
				cnt++;
				e = m.end;

			}
		}
		System.out.println(cnt);

	}

}

class Meeting implements Comparable<Meeting> {
	int start;
	int end;

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

	@Override
	public int compareTo(Meeting m) {
		//끝나는 시간이 빠른 순서로 정렬, 끝나는 시간이 같을 때는 시작하는 시간 순서로 정렬 (오름차순)
		if (this.end == m.end)
			return this.start - m.start;
		return this.end - m.end;
	}
}

 

 

풀이

 

그리디greedy 알고리즘:

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

 

 

그리디 알고리즘의 핵심 이론

① 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택

 

② 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사

 

③ 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 ①로 돌아가 같은 과정 반복

---

현재 회의의 종료시간이 빠를수록 다음 회의가 겹쳐지지 않게 시작하는데 유리!

-> 종료 시간이 빠른 순서대로 정렬해 겹치지 않는 회의실을 적절하게 선택

 

 

① 회의 정보를 종료 시간 순으로 정렬. 단, 종료 시간이 같을 때는 시작 시간을 기준으로 다시 한번 정렬

-> 우선순위큐,  meeting 객체 사용

 

② 순차적으로 탐색( 전 회의의 종료 시간이 다음 회의의 시작 시간보다 빠르면 선택

-> 종료시간을 선택한 종료시간으로 바꿔주고 cnt++