Simple O(n) solution, just subtract non-poisoned time from max possible poisoned time

  • 0

    The maximum possible poisoned duration is the last element of timeSeries + duration. Simply keep track of the end of the current poisoned interval and iterate through timeSeries, subtracting off a chunk of time whenever the start of an interval comes after the end of current one.

        if not timeSeries: return 0
        ans = timeSeries[-1] + duration
        end = 0
        for t in timeSeries:
            if t > end: ans -= t-end
            end = t + duration
        return ans

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.