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

[1.문제이해]

Play시간에 대한 구간정보가 주어지고, 시청자들이 가장 많이 보는 구간정보들이 주어질때, 이때 광고의 누적재생수가 최대인 지점의 시작지점을 반환하면된다.

[2.알고리즘 접근]

- 공통적인 절차

1. 먼저 시,분,초의 Format을 flat하게 만들어야한다. 시간=>초
2. PlayTime에 해당하는 모든 구간에 관해서 들어오고, 나가는 지점에 대한 In And Out을 기록한다.
3. 구간에 해당하는 누적재생수가 최대인 지점을 구하기 위해서는 누적합을 이용할 필요가 있다.
   예를 들면 다음과 같다.
   

   구간별 들어오는 시점에 관해서 1을 표시 나가는 지점에 대해 -1을 표시했다.
   이들의 합을 통해 구간별 In and Out을 알 수 있다.
   그리고 In and Out의 누적합 방식을 이용하면 구간별 재생수를 알 수 있다.
   이에 관해 한번더 누적합 방식을 이용하면 누적 재생수를 알 수 있다.

누적합 활용

1. Only 누적합 방식

SumArray[i]+=SumArray[i-1]방식으로 계속해서 만들어 나가는데. 해당지점 [i,j]에 관해서 구할려면 SumArray[j]-SumArray[i]를 하면된다.

자세한 절차는 다음과 같다.
1.PlayTime에 해당하는 모든 구간에 관해서 들어오고, 나가는 지점에 대한 InAndOut을 기록한다.

2. 투포인터+누적합 방식.

새롭게 들어오는 재생수에 관해서 더하고 꼬리지점(Start지점)에 해당하는 재생수를 빼면서 비교한다. 이때 [ 꼬리 , 머리 ]구간은 광고의 길이이다.
[ 꼬리 , 머리 ]구간 에서 [ 꼬리+1 , 머리+1 ]로 넘어갈때,
Array[머리+1]=Array[머리]+Play[머리+1]-Play[꼬리] 이런식으로 구하면 된다.

[3.구현]

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int convert(string str)
{
    int hour = stoi(str.substr(0)) * 3600;
    int min = stoi(str.substr(3)) * 60;
    int sec = stoi(str.substr(6));
    return hour + min + sec;
}
struct Record
{
    ll sum = 0, start = 0, end = 0;
} record, temp;
string convertTostr(int time)
{
    string answer;
    int hour = time / 3600;
    int min = (time % 3600) / 60;
    int sec = (time % 60);
    string stime[3]{to_string(hour), to_string(min), to_string(sec)};
    for (auto &t : stime)
    {
        if (t.size() == 1)
            answer += "0";
        answer += t + ":";
    }
    answer.pop_back();
    return answer;
}
ll SumArray[360001];
string solution(string play_time, string adv_time, vector<string> logs)
{
    int playtime = convert(play_time);
    int advtime = convert(adv_time);
    for (auto &log : logs) //1. In and Out구하기
    {
        int start_ = convert(log.substr(0, 8));
        int end_ = convert(log.substr(9));
        ++SumArray[start_];
        --SumArray[end_];
    }
    for (int i = 1; i < playtime; i++) //2. 구간별 재생수구하기
        SumArray[i] += SumArray[i - 1];
    for (int i = 1; i < playtime; i++) //3. 누적재생수 구하기
        SumArray[i] += SumArray[i - 1];
    record.sum=SumArray[advtime];
    for (int start = advtime+1; start < playtime; start++)
    {
        ll Sum = SumArray[start] - SumArray[start - advtime];
        if (Sum > record.sum)
        {
            record.start = start-advtime+1;
            record.sum = Sum;
        }
    }
    return convertTostr(record.start);
}