Teemo Attacking Problem


Description

LeetCode Problem 495.

Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly duration seconds. More formally, an attack at second t will mean Ashe is poisoned during the inclusive time interval [t, t + duration - 1]. If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will end duration seconds after the new attack.

You are given a non-decreasing integer array timeSeries, where timeSeries[i] denotes that Teemo attacks Ashe at second timeSeries[i], and an integer duration.

Return the total number of seconds that Ashe is poisoned.

Example 1:

1
2
3
4
5
6
Input: timeSeries = [1,4], duration = 2
Output: 4
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 4, Teemo attacks, and Ashe is poisoned for seconds 4 and 5.
Ashe is poisoned for seconds 1, 2, 4, and 5, which is 4 seconds in total.

Example 2:

1
2
3
4
5
6
Input: timeSeries = [1,2], duration = 2
Output: 3
Explanation: Teemo's attacks on Ashe go as follows:
- At second 1, Teemo attacks, and Ashe is poisoned for seconds 1 and 2.
- At second 2 however, Teemo attacks again and resets the poison timer. Ashe is poisoned for seconds 2 and 3.
Ashe is poisoned for seconds 1, 2, and 3, which is 3 seconds in total.

Constraints:

  • 1 <= timeSeries.length <= 10^4
  • 0 <= timeSeries[i], duration <= 10^7
  • timeSeries is sorted in non-decreasing order.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        if (timeSeries.size() == 0)
            return 0;
        int res = 0;
        for (int i = 0; i < timeSeries.size()-1; i++) {
            if (timeSeries[i+1] - timeSeries[i] < duration)
                res += timeSeries[i+1] - timeSeries[i];
            else
                res += duration;
        }
        return res + duration;
    }
};




Related Posts

Walking Robot Simulation Problem

LeetCode 874. A robot on an infinite XY-plane starts at...

Valid Mountain Array Problem

LeetCode 941. Given an array of integers arr, return true...

Sum Of Even Numbers After Queries Problem

LeetCode 985. You are given an integer array nums and...

Partition Array Into Disjoint Intervals Problem

LeetCode 915. Given an integer array nums, partition it into...

Monotonic Array Problem

LeetCode 896. An array is monotonic if it is either...

Maximize Distance To Closest Person Problem

LeetCode 849. You are given an array representing a row...