백준 1931번 자바☆

문제

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

1931번: 회의실 배정

 

1. 접근 방식

역시 그리디 관련 문제는 처음 접근이 가장 중요한것 같다..

 

처음 접근을 회의 시작시간을 정렬하는 방법으로 했는데 결국 점점 산으로가 포기했다.

정답은 회의 종료시간 순으로 정렬을 시키고 종료시간이 같을 경우 시작시간 순으로 정렬을 해야한다.

 

해당 접근만 주의하면 크게 어렵지 않은 문제다.

 

2. 구현

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

public class Main {

	static int N;
	static Convention[] conventions;
	static int cnt;
	
	static class Convention implements Comparable<Convention> {
		long start;
		long end;

		public Convention(long start, long end) {
			this.start = start;
			this.end = end;
		}

		@Override
		public int compareTo(Convention o) {
        	//종료시간이 같다면 시작시간 순으로 정렬
			if (this.end == o.end) {
				return (int)(this.start - o.start);
			}
			return (int)(this.end - o.end);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		conventions = new Convention[N];
		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());
			int gap = end - start;
			conventions[i] = new Convention(start, end);
		}
		Arrays.sort(conventions);
		
		long end = -1;
		for (int i=0; i<N; i++) {
			if (conventions[i].start >= end) {
				end = conventions[i].end;
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}