백준 1931번: 회의실 배정 [정렬][그리디][Greedy] -Java

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

1931번: 회의실 배정

그리디 알고리즘의 문제!

여러가지 경우의 수를 다해보면서 최적의 알고리즘을 알아내보자..

 

이번 문제는 회의실을 가장 효율적으로 많이 사용하는 방법의 갯수를 찾는 것이 관건이다.

회의시간이 빨리 끝나는 순서대로 정렬을 하여 배치를 한다.

 

 

 

Java코드 참고하세욤...

728x90

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int res = 0;
		ArrayList<Meeting> list = new ArrayList<Meeting>();	
		//입력
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			list.add(new Meeting(s,e));
		}
		
		//정렬
		//회의 끝나는 시간이 가장 빠른순서대로, 같은경우 시작시간이 빠른순
		Collections.sort(list, new Comparator<Meeting>() {
			
			@Override
			public int compare(Meeting m1, Meeting m2) {
				if(m1.end < m2.end)
					return -1;
				else if (m1.end == m2.end) {
					if (m1.start > m2.start)
						return 1;
					else if (m1.start == m2.start)
						return 0;
					else
						return -1;
				} else 
					return 1;
			}
		});
		
		int curTime = list.get(0).end;
		res ++;
		for (int i = 1; i < N; i++) {
			Meeting m = list.get(i);
			
			if(m.start < curTime)
				continue;
			
			curTime = m.end;
			res ++;
		}
		
		System.out.println(res);
	}

}

class Meeting {
	int start;
	int end;
	
	public Meeting (int s, int e) {
		this.start = s;
		this.end = e;
	}
}

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