그리디를 통해 풀 수 있는지 먼저 고민해봤다.
특정 회의를 선택하면 그 뒤에도 계속해서 최적의 해가 되지 않을까
0시간 부터 탐색한다고 가정했을때, 가장 빨리 끝나는 회의부터 선택을 한다면 최적의 해가 된다.
각 회의는 시작시간, 끝시간을 가지고 있으므로 정렬이 필요한데, Comparator 사용하면 쉽게 우선순위대로 정렬이 가능하다.
PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return Long.compare(o1.e, o2.e);
}
});여기선 PQ를 사용했는데, Collections를 사용해도 동일하다.
놓친점 1
계속해서 85%에서 실패했다.. 그 이유는 조건을 상세히 보면 시작시간과 끝나는 시간은 자연수 범위이다.
즉, 회의가 시작하는 시점과 끝나는 시점이 동일한 자연수일 수 도 있다. 이렇게 되면 동일한 시간에 끝나는 회의가 여러개 존재할 수 있으므로, 먼저 시작하는 회의부터 선택해야 한다.
일반적인 상식으로는 "하나의 회의실에서 동일한 회의가 여러개 끝날 수 없다" 여기서는 조건이 조금 다르므로 잘 캐치해야 한다.
