광고 삽입

• 구간 업데이트와 구간 쿼리가 섞여있다보니 세그먼트 트리가 필요할 것 같지만, 구간 업데이트가 모두 끝난 뒤에 쿼리들이 나올 때에는 prefix sum만을 이용해서 더 빠르게 풀 수 있다. 방법은 구간 합을 참고.
• O(|logs|)에 구간 업데이트를 처리한 뒤, O(play_time)으로 누적 합을 계산한다. 누적합을 계산하고 나면 길이가 adv_time인 각각의 구간의 구간합을 O(1)에 계산할수 있으므로, 모든 구간 중 구간합이 최대값인 구간을 찾는 것은 구간의 갯수인 O(play_time - adv_time) 이다. 그래서 전체 시간 복잡도는 O(n+m), (n=로그의 갯수, m는 플레이타임)
• 구현하지는 않았지만, 다른 방법으로는 스위핑을 사용하는 방법도 있다. 로그의 시작과 끝 두종류 이벤트를 모아서 시간순으로 정렬한 다음, 순서대로 프로세싱하는 방법을 사용하면, m과 관계 없이 O(nlogn)의 시간복잡도로 처리할 수도 있다.

"""Solution code for "Programmers 72414. 광고 삽입".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/72414
- Solution link: http://www.teferi.net/ps/problems/programmers/72414
"""


def time_to_secs(time):
    h, m, s = [int(x) for x in time.split(':')]
    return (h * 60 + m) * 60 + s


def solution(play_time, adv_time, logs):
    play_time_sec = time_to_secs(play_time) + 1
    range_diff = [0] * play_time_sec
    prefix_sum = [0] * play_time_sec
    for log in logs:
        beg, end = [time_to_secs(x) for x in log.split('-')]
        range_diff[beg] += 1
        range_diff[end] -= 1

    range_count = 0
    for i in range(1, play_time_sec):
        prefix_sum[i] += prefix_sum[i - 1] + range_count
        range_count += range_diff[i]

    adv_time_sec = time_to_secs(adv_time)
    max_view = max((prefix_sum[t + adv_time_sec] - prefix_sum[t], -t)
                   for t in range(play_time_sec - adv_time_sec))
    best_time = -max_view[1]
    hh, mm, ss = best_time // 3600, best_time % 3600 // 60, best_time % 60
    return f'{hh:02d}:{mm:02d}:{ss:02d}'