No1931 회의실 배정 (그리디 알고리즘)

본 문제는 그리디 알고리즘을 사용하여 매 선택마다 최적의 답을 구하는 문제이다.

 

아래 블로그의 글을 참고하였다.

https://hongjw1938.tistory.com/172

알고리즘 - 그리디 알고리즘(Greedy Algorithm)

 

시작 시간과 종료 시간을 가지고 있는 여러 회의들을 시간이 겹치기 않고 가장 많이 담을 때 총 개수를 구하는 문제이다.

핵심은

1. 다음 단계의 회의를 선택할 때 .조건은 전 회의 종료 시간보다 다음 단계의 회의  시작 시간이 늦거나 같아야 한다. 

2. 다음 단계의 회의를 선택할 때  종료시간이 가장 짧은 회의를 선택하는 것의 최적의 답이다.

 

즉, 다음 단계의 회의를 선택할 때  (1) 전 회의의 종료 시간보다 다음 회의 시작 시간이 같거나 늦어야 하고 (2) 그 중에 종료 시간이 가장 짧은 회의를 선택해야 한다.

 

이를 위해 시작 시간과 종료 시간이라는 두 필드를 갖는 클래스를 생성했다.

그리고 이 클래스를 담고 있는 리스트를 종료 시간이 짧은 순으로 정렬하였다.

구현한 코드는 아래와 같다.

 

package com.yuk;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

public class No1931 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		ArrayList<Mt> list = new ArrayList<>();
		
		while(N-- > 0) {
			String[] strArr =br.readLine().split(" ");
			int x = Integer.parseInt(strArr[0]);
			int y = Integer.parseInt(strArr[1]);
			list.add(new Mt(x,y));
		}
		
		list.sort(new Comparator<Mt>() {

			@Override
			public int compare(Mt o1, Mt o2) {
				if(o1.y==o2.y) {
					return o1.x-o2.x;
				}
				return o1.y-o2.y;
			}
		});
		
		int cnt = 0;
		int pre = 0;
		while(true) {
			int endTime = list.get(pre).y;
			cnt++;
			boolean flag = false;
			for(int i=pre+1; i<list.size(); i++) {
				if(list.get(i).x>=endTime) {
					pre=i;
					flag = true;
					break;
				}
			}
			if(!flag) break;
		}
		System.out.println(cnt);		
	}
}

class Mt {
	int x;
	int y;
	
	public Mt(int x, int y) {
		this.x = x;
		this.y = y;
	}
}