모든 시간 간격의 겹치기 최대 수

Question

시간 간격이 설정된 경우 겹치는 부분의 최대 수를 찾는 방법은 다음과 같습니다. 시간 복잡도 O (n log n) 또는 O (n)과 주어진 문제를 해결하는 알고리즘이 있습니까 ??

예 : (6 : 00-9 : 30), (9 : 00-12 : 30), (10 : 00-10 : 30), (12 : 00-14 : 30) -13 : 30). 대답은 3입니다.

Answer 1

빠른 정렬 - O(nlogn) 시간을 사용하여 값을 정렬하십시오.

6:00(+) 
9:30(-) 
9:00(+) 
12:30(-) 
10:00(+) 
10:30(-) 
12:14:30(Dude wut?) --> Im going to assume you meant 12:00(+) ,14:30(-) 
11:00(+) 
13:30(-) 

모든 플러스 증가 및 모든 빼기 위해 감소시키는 목록을

6:00(+) 
9:00(+) 
9:30(-) 
10:00(+) 
10:30(-) 
11:00(+) 
12:00(+) 
12:30(-) 
13:30(-) 
14:30(-) 

반복 처리를하게되고, 발견 된 최대 값을 기록한다. 이

총 시간에 따라 다르다 O(nlogn + n) = O(nlogn)