[2018 카카오 기출] 추석 트래픽(JAVA)

https://programmers.co.kr/learn/courses/30/lessons/17676

---

시뮬레이션 문제입니다.

 

1. 계산의 편의성을 위해서 시간 정보 String을 파싱해서 double 값으로 비교 연산을 수행했습니다.

2. 1초의 범위를 계산해볼 기준이 되는 구간은 로그 문자열 한 줄의 시작시간과 끝 시간입니다.

 

그 이유는 두 개 이상의 구간이 겹쳤을 때 겹치는 구간의 시작점 상한, 하한은 어느 한 로그 문자열의 시작점과 끝점입니다.

다시 말하면 정답이 나오는 구간은 최소 하나의 로그 문자열은 시작점과 끝점을 포함할 수 있습니다.

 

정답이 나오는 구간이 모든 로그 문자열의 중간 지점에서도 나올 수 있지만, 

그 구간을 조금만 앞이나 뒤로 밀어서 하나의 로그 문자열의 시작점과 끝점에 맞춰도 여전히 정답이 나오는 구간이라는 뜻입니다.

 

그래서 로그 문자열의 갯수가 N개라고 했을 때 저희가 최대 트래픽 발생 지점으로 조사해 볼 구간은 2N개입니다.

(각 로그 문자열의 시작점, 끝점을 N번 연산)

 

N 제한이 작으므로 한 번 연산할 때 전체 로그 문자열을 순회해도(O(N^2) 됩니다.

---

코드: https://github.com/cotchan/algorithm/blob/main/java/PROGRAMMERS/PG17676.java