백준 1931 회의실 배정
Quick Sort의 시간복잡도
Quick sort의 시간복잡도는 경우에 따라 다양하다. 보통의 경우 nlog₂n이 소요된다.
하지만 최악의 경우, 즉 리스트가 불균형하게 나누어지는 경우 n² 만큼 소요된다.
예를 들면, 이미 정렬된 리스트가 해당된다.
pivot을 첫번째 값으로 설정할 경우, 순환 호출의 횟수가 n에 해당하고, 각 호출 단계에서 비교 연산도 n회가 되므로, O(n²) 만큼이 소요된다.
따라서 퀵 정렬 이용 시, 시간 초과가 나온다. 따라서 병합 정렬을 이용한다.
끝나는 시간 순으로 정렬
회의실 시간에 경우
0 2
2 4
6 10
4 6
5 10
12 14
..
이런식으로 들어온다. 하나의 쌍을 끝나는 시간 순으로 정렬한다. 하지만 문제가 되는 경우가 있는데, 이는 끝나는 시간이 같지만, 시작 시간이 다른 경우다. 위의 예시를 토대로 가정해보자.
시작시간을 고려하지 않고 정렬한 결과
2 2
0 2
4 6
9 10
8 10
12 14
이런식으로 되었다고 해보자.
처음 2-2, 0-2 부분에서 0-2가 먼저 나온다면 0-2 회의를 진행 후, 2-2 회의를 진행할 것이다. 하지만, 시작시간순을 고려하지 않은 상황은 2-2를 먼저 진행해서 0-2 회의를 진행하지 못한다. 따라서 끝나는 시간이 같을 때, 시작시간 또한 고려하여야 한다.
