[백준1931] 회의실 배정 / Java

링크 | https://www.acmicpc.net/problem/1931

문제 |

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

입력 |

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

출력 |

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

예제 |

입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

출력

4

Solution |

• 활동 선택 문제: 각각 시작시간과 종료시간으로 표시된 활동이 주어진 시간 내에 충돌하지 않고 수행할 수 있도록 하는 최적의 조합을 구하는 문제.

• 종료시간 오름차순->시작시간 오름차순 정렬

• 제일 빨리 끝나는 활동을 시작으로 정렬된 활동시간들을 비교하여 겹치는 경우는 제외하고 선택하다보면 최적의 조합을 구할 수 있게 된다.

예제) 제일 빠른 종료시간을 가진 활동 = (1, 4)
(1, 4) -> (5, 7) -> (8, 11) -> (12, 14)

• 2차원 배열 정렬 (참고 ↓ ↓ ↓ )
  Arrays.sort(arr, new Comparator<int[]>() { 
       @Override
       public int compare(int[] o1, int[] o2) {
             return o1[0]-o2[0]; // 첫번째 숫자 기준 오름차순
             //return o2[0]-o1[0]; // 첫번째 숫자 기준 내림차순
             //return o1[1]-o2[1]; // 두번째 숫자 기준 오름차순
             //return o2[1]-o1[1]; // 두번째 숫자 기준 내림차순

            // 첫번째 기준 오름차순 > 두번째 기준 오름차순
           //return o1[0]!=o2[0] ? o1[0]-o2[0] : o1[1]-o2[1];
           // 첫번째 기준 오름차순 > 두번째 기준 내림차순
           //return o1[0]!=o2[0] ? o1[0]-o2[0] : o2[1]-o1[1];
      }

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

public class AssignedRoom {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int act[][] = new int[N][2];
		StringTokenizer split;
		
		for(int i=0; i<N; i++) {
			split = new StringTokenizer(br.readLine(), " ");
			act[i][0] = Integer.parseInt(split.nextToken());
			act[i][1] = Integer.parseInt(split.nextToken());
		}
		
		//종료시간 오름차순 정렬 후, 시작시간 오름차순
		Arrays.sort(act, new Comparator<int[]>(){
		    @Override
		    public int compare(int[] o1, int[] o2) {
		        return o1[1]!=o2[1] ? o1[1]-o2[1] : o1[0]-o2[0];
		    }
		});
		
		int nextstart = 0, cnt=0; 
		for(int i=0; i<N; i++) {
			if (act[i][0] >= nextstart) {
				nextstart = act[i][1];
				cnt++;
			}
		}
		System.out.println(cnt);
	}
}