問題

曲の入った2つのアルバムが与えられる.

曲の長さは duration1, duration2 の配列で与えられる.

minutes 秒間の間にきくことが可能な曲の数を答えよ。

ただし、制約として T 個の曲をそれぞれのアルバムから必ず選択しなければならない.

方針

やや難しいシミュレーション問題。

後半で場合わけを頑張ったけど、場合わけしない解法があったようだ。

(両方のアルバムをマージして、数の小さいものから取り出す)

解答

class ListeningSongs:
    def listen(self, durations1, durations2, minutes, T):
        s1 = len(durations1)
        s2 = len(durations2)

        if s1 < T or s2 < T:
            return -1

        durations1 = list(durations1)
        durations2= list(durations2)

        d1 = sorted(durations1)
        d2 = sorted(durations2)

        t = minutes * 60

        cnt = 0

        for i in range(T):
            t -= d1[i]
            t -= d2[i]
            cnt += 2

        if t < 0:
            return -1

        i1 = T
        i2 = T


        while(t >= 0):
            if i1 == s1 and i2 < s2:
                t -= d2[i2]
                i2 += 1
            elif i2 == s2 and i1 < s1:
                t -= d1[i1]
                i1 += 1
            elif i1 == s1 and s2 == i2:
                break
            else:
                if d1[i1] < d2[i2]:
                    t -= d1[i1]
                    i1 += 1
                else:
                    t -= d2[i2]
                    i2 += 1
            if t >= 0:
                cnt += 1
        return cnt