(M - 729. My Calendar I) Case 분류 + Parametric search

Case 분류 사진 추가 요망

 

Brute Force - 그냥 저장해놓은 기록들 일일히 비교하면서 conflict 일어나는지 체크

O(N^2) - N이 작아서 통과

 

더 최적화?

굳이 일일히 다 비교할 필요 있나?

중간 쯤에 비교 대상이 있으면, 앞 뒤 부분에는 애초에 겹칠 가능성이 없는 애들이 잔뜩 있을텐데!

→ Sorting 유지해서, binary search로 비교할 대상만 pin-point 서치 한다면?

 

Sorting 유지해주는 자료구조 : set, map (C++의 경우)

Case분류에 따른 기준을 잘 세워야 함.

 

Sol 2

난 start 끼리 비교해서 Case 1, 3 커버하고, 반환 iter 이전의 값까지 비교해서 Case 2, 4 커버.

 

Sol 3

근데, start와 evt.End를 비교하면 모든 케이스 커버 가능.