[アルゴリズム]秋夕流量

プログラマー2018 KAKAO BLIND RECRUITMENTコードテストでの質問
中秋節の流量問題

ぶんせき

流量の開始時間と終了時間を求め、1秒で最も流量が多い瞬間の個数が答えです.
グリディアルゴリズムを用いて解くことができるようだ.

1.タイミング

流量が終了した時間と流量が終了した時間の2つの時点から流量が開始した時間と流量が終了した後1秒の時点を求めることができる.
もとは秒、分、時を計算する時は「120秒=2分」です.

minute += second//2
second -= second%60

上記の場合、サーバのタイムアウト時間は3秒=sを超えないので、減算してもよい.
開始時間を求めるときは、終了時間を外します.
流量が終わってから1秒が過ぎて、終わった時間にもう1秒すればいいです.
このように計算が終了すると、[開始時間,終了時間+1]という形でタイムリストに追加される.

2.最大流量を得る

[終了時間+1]を基準に時間リストをソートします.
そして2回繰り返して、時間を1つずつ比較します.0時間目を基準に1時間目からn時間目まで3時間目を基準に4時間目からn時間目まで比較します.
基準時間の[終了時間+1]が比較時間の[開始時間]よりも大きい場合、カウントは1つずつ上げられる.[終了時間+1]を基準に並べ替えられているので、開始時間が先であれば範囲内に含まれます.

3.小数点の問題

二つのケースがあります
CASE1: ["2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"]
CASE2: ["2016-09-15 01:00:04.002 2.0s", "2016-09-15 01:00:07.000 2s"]
case 1は1、case 2は2です.このオーバーラップ部分はfloat変数の計算により問題が発生したため,1秒後の時間を0.999秒後の時間に変更した.

コード#コード#

def goTime(time, s): # ①
    time[2]+=s
    if time[2]>=60: 
        time[2]-=60
        time[1]+=1
    elif time[2]<0:
        time[2]+=60
        time[1]-=1
    if time[1]>=60: 
        time[1]-=60
        time[0]+=1
    elif time[1]<0:
        time[1]+=60
        time[0]-=1
    return time

def solution(lines):
    times, answer = [], 0
    for i in lines: ①
        time=i[11:23].split(':')
        sTime= goTime([int(time[0]),int(time[1]),float(time[2])], -float(i[24:-1]))
        eTime = goTime([int(time[0]),int(time[1]),float(time[2])], 0.999) # ③
        times.append([sTime, eTime])
    times.sort(key=lambda x: (x[1],x[0])) # ②
    
    for i in range(len(times)): ②
        tmp = 0
        for j in range(i,len(times)):
            if times[i][1]>times[j][0]: tmp+=1     
        answer=max(answer, tmp)
    return answer