첫 아이디어
계속 생각해도 적절한 아이디어가 떠오르지 않았다.
생각한 아이디어는
- 같은 시작 시간인데 비효율적인 걸 제거하자(3->5 | 3->8)
- 3차원 배열로 저장해서 시작시간,종료시간,효율성(종료시간-시작시간)
- 최대의 회의실 = 짧은 시간이면서 시간이 딱 잘 맞아떨어지는..
이런 저런 생각을 해도 마땅히 떠오르지가 않았다.
💡 해결 및 코드
결국 고민하다가 검색을 했는데 내가 생각도 못한 방식이 있었다.
일단 최대의 회의실을 차지한다는 것은
- 겹치지 않는 활동
- 종료시간이 더 빠른 것들부터
라는 조건이었고 겹치지 않는다는 것은 당연했으나, 종료시간을 기준으로 정렬해서 문제를 해결할 생각은 아예 못하고 있었다..
📋 이러한 문제들이 나올 때 어떻게 알아볼까?
시간표를 최대한 많이 배정하거나 선택하는 문제들을 활동 선택 문제라고 부른다고들 한다..한 번에 하나의 처리 과정만 할 수 있을 때에 최대한 많이 처리하도록 하는 문제들을 이렇게 일컷는다고 한다.
우리가 하나의 과정을 선택하면 그 과정 중에는 아무것도 할 수 없다. 회의실이 하나뿐인데 이미 회의중이라면 우리가 할 수 있는 것은 없는 것처럼 말이다. 이걸 다른 의미로는 하나의 활동을 시작해서 하고 있다면 나머지 활동들에 대해서 독립적이라는 말을 할 수 있다!!
💻 코드
import java.io.*;
import java.util.*;
public class Main {
/*
같은 시간인데 비효율적인 걸 빼자?
최대의 회의 -> 짧으면서도 물레가 맞게 돌아가도록?
-------------------------------
겹치지 않는 활동에 대해 종료시간이 더 빠르면 더 많은 활동!
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int startNum = Integer.parseInt(st.nextToken());
int[][] times = new int[startNum][2];
for(int i = 0 ; i < startNum; i++){
st = new StringTokenizer(br.readLine());
times[i][0] = Integer.parseInt(st.nextToken());
times[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(times, 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 curTime= 0;
for(int i = 0 ; i < startNum; i++){
if(curTime <= times[i][0]){//시작 : 현 시각 <= 꺼내온 시간의 시작 시간
curTime = times[i][1];
cnt++;
}
}
System.out.println(cnt);
}
}
