[BOJ] BOJ1931 회의실 배정

문제

BOJ1931_회의실배정

풀이

탐욕(그리디) 알고리즘

• 최적해를 구하는 데 사용되는 근시안적인 방법
• 최적화 문제(optimization) : 가능한 해들 중에서 가장 좋은(최대 or 최소) 해를 찾는 문제
• 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
• 한 번 선택된 것은 번복 X

회의실 클래스을 만들어서 회의의 시작시간과 종료시간을 관리해주었다. 종료 시간 순으로 활동들을 정렬하면 뒤에 오는 활동들은 나보다 늦게 끝난다는 전제가 가능하기 때문에 Comparable을 이용하여 클래스 정렬 기준을 종료 시간순으로 두었다. 그리고 회의 시작과 동시에 종료되는 경우도 존재하기 때문에 비교한 종료 시간이 동일하다면 시작시간 순으로 정렬해주었다. 그리고 MeetingRoom배열을 이용하여 현재 회의 시작시간이 앞서 배정되었던 회의 종료시간보다 크거나 같다면 배정 횟수를 +1 해주고 endTime=m[0].end과 같이 배정된 회의의 종료시간을 현재 회의의 것으로 변경하였다.

JAVA 코드

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

public class Main {

	
	static class MeetingRoom implements Comparable<MeetingRoom>{
		int no,start,end; //회의실 번호, 시작,종료 시간

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

		@Override
		public int compareTo(MeetingRoom arg0) {
			int diff = this.end-arg0.end; //종료시간 기준으로 오름차순 정렬
			return diff!=0?diff:this.start-arg0.start; //종료시간이 같다면 시작 시간으로 정렬
		}

		@Override
		public String toString() {
			return "MeetingRoom [no=" + no + ", start=" + start + ", end=" + end + "]";
		}
		
		
		
		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st;
		MeetingRoom[] m = new MeetingRoom[N];
		
		
		for(int i=0;i<N;i++) {
			
			
			st = new StringTokenizer(br.readLine());
			m[i] = new MeetingRoom(i+1, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			
			
		}

		int ans = getCnt(m);
		System.out.println(ans);
		
	}

	public static int getCnt(MeetingRoom[] m) {
		Arrays.sort(m);
		int endTime = m[0].end;
		int cnt=1;
		for(int i=1,size=m.length;i<size;i++) {
			if(endTime<=m[i].start) {
				endTime=m[i].end;
				cnt++;
			}
		}
	
		return cnt;
	}

}