1931문제 회의실 배정(그리디) Java

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

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

 

출처: <https://www.acmicpc.net/problem/1931>
 

1931번: 회의실 배정

 

##문제이해##

0시부터 24시까지 존재한다고 가정했을때

각각 0~24까지 가장 적은시간을 필요로하는 걸 찾아서 안겹치는걸 비교해서 가져온다.

안겹치는부분을 어떻게 해야하는지를 고민하다..결국 직접비교를 수행했다.

 

##기타사항##

 시작시간과 끝시간을 비교하는것과 원하는 방식으로 정렬시키는게 포인트 인것 같다.(ex 1~4 -->5~7)

예제로 주어진 코드의 경우 sort을 하든 안하든 동일한 값을 가지고있어서 처음에는 sort을 안한상태로 진행했었는데.. 틀렸다고 떠서 참고했다

##참고한 블로그##

https://st-lab.tistory.com/145

[백준] 1931번 : 회의실배정 - JAVA [자바]

 

##내 코드##

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class boj_1931 {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		
		
		/*
		  time[][0] 은 시작시점을 의미 
		  time[][1] 은 종료시점을 의미 
		*/
		int[][] time = new int[N][2];
		
		
		for(int i = 0; i < N; i++) {
			time[i][0] = in.nextInt();	// 시작시간 
			time[i][1] = in.nextInt();	// 종료시간 
		}
		//종료시간 기준으로 정렬
		Arrays.sort(time,new Comparator<int[]>() {
			//비교부분
			@Override
			public int compare(int[] o1, int[] o2) {
				//종료시간이 만약 같은경우에는 시작시간 순서로 정렬
				if(o1[1]==o2[1]) {
					return o1[0]-o2[0];
				}
				return o1[1]-o2[1]; //종료시간 기준으로 정렬
			}
		});
		//뒤에서부터 종료시간과 시작시간이 짧은걸 체크하기 시작한다.
		int cnt =0;
		int end= 0;//시간 초기셋팅
		for(int i=0; i<N; i++) {
			// 직전 종료시간이 다음 회의 시작 시간보다 작거나 같다면 갱신 
			if(end <= time[i][0]) {
				end = time[i][1];
				cnt++;
			}
		}
		System.out.println(cnt);
		
	}

}