[Java][1931] 회의실 배정

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

1931번: 회의실 배정

코드:

import java.util.*;

public class Main {
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt(); // 회의 수
    	Room [] r = new Room[n];
    	
    	for(int i=0;i<n;i++) {
    		// 회의 시간
    		r[i] = new Room(sc.nextLong(),sc.nextLong());
    	}

    	// 시작 시간 오름차순 정렬
    	Arrays.sort(r);
    	
    	// 끝 시간 오름차순 정렬
    	Arrays.sort(r,new Comparator<Room>() {
    		public int compare(Room r1,Room r2) {
    			if(r1.end > r2.end) {
    				return 1;
    			}else if(r1.end == r2.end) {
    				return 0;
    			}else {
    				return -1;
    			}
    		}
    	});
    	
    	/*
    	// 정렬 확인용
    	for(int i=0;i<n;i++) {
    		// 회의 시간
    		System.out.println(r[i].end);
    	}
    	*/
    	
    	int cnt = 1;
    	long cur = r[0].end;
    	for(int i=1;i<n;i++) {
    		if(r[i].start >= cur) {
    			cnt++;
    			cur = r[i].end;
    		}
    	}
    	
    	System.out.println(cnt);
    }
}

class Room implements Comparable<Room>{
	long start;
	long end;
	
	public Room(long start,long end){
		this.start = start;
		this.end = end;
	}
	
    // 시작 시간 오름차순 정렬
	public int compareTo(Room r) {
		if(this.start > r.start) {
			return 1;
		}else if(this.start == r.start) {
			return 0;
		}else {
			return -1;
		}
	}
}

 

위 문제는 회의 끝 시간을 오름차순 정렬 한 뒤 차례대로 시간을 잡아 푸는 문제이다. (그리디)

 

예를 들어 회의가 [1, 2], [2, 9], [3, 6], [4, 8] 이렇게 4개 있다면

[1, 2], [3, 6], [4, 8],[2, 9] 순으로 정렬 할 수 있고 차례대로 [1, 2] ,[3, 6] 으로 선택하면 최대로 많은 회의를 진행할 수 있다.

 

회의 시간이 주어질 때 [1, 4], [8, 8], [4, 8] 순으로 주어질 경우 차례대로 선택하면 [4, 8]을 고를 수 없어

최대한 많은 회의가 진행되도록 할 수 없다.

 

그러므로 시작시간을 기준으로 오름차순 정렬을 한 뒤 다시 회의 끝 시간을 오름차순 정렬하고

차례대로 가능한 시간을 선택한다면 최대한 많은 회의가 진행되도록 할 수 있다.