Teemo Attacking

Problem Statement

In this scenario, we delve into the fantasy world where Teemo attacks Ashe using poisoned darts. Each dart attack from Teemo poisons Ashe for a specified number of seconds ("duration"). To elaborate, a dart attack at time t results in Ashe being poisoned from time t to t + duration - 1 inclusively. However, should another dart hit Ashe during an ongoing poison effect, this freshly administered poison overlaps and extends the duration starting anew from that point in time.

The objective is to compute the total number of seconds Ashe remains poisoned, given a series of attack times and a poison duration. The attack times are listed in a timeSeries array (whose values are in non-decreasing order). This problem not only tests basic iteration and condition checking but also requires careful handling of overlapping intervals and sum calculations.

Examples

Example 1

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

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 <= 104
• 0 <= timeSeries[i], duration <= 107
• timeSeries is sorted in non-decreasing order.

Approach and Intuition

Understanding the dynamics of the problem revolves around overlapping and non-overlapping intervals of time. Here's a step-by-step breakdown to approach the solution:

1. Initialize a variable to keep track of the total poisoned duration. Let's call it totalPoisonDuration.
2. Traverse through the timeSeries array which contains timestamps of each of Teemo's attacks.
3. For the first attack in the series, simply consider Ashe poisoned for the full duration since there’s no previous attack to consider for overlap.
4. For each subsequent attack:
   • Check if it occurs before the poison from the previous attack would have worn off.
   • If it does, it means there's an overlap, and rather than adding the whole duration, add only the portion from the attack time till what would have been the end of the previous poison effect.
   • If it doesn't overlap, just add the full duration to the totalPoisonDuration.
5. Move to the next attack till all attacks are accounted for.

This approach ensures that each section of the poisoned duration is considered without redundancy, giving the accurate total time Ashe remains affected by the poison. The correct and efficient accumulation of these poison intervals, whether they are overlapping or not, leads to the final solution.

Solutions

class Solution {
  public int calculatePoison(int[] series, int time) {
    int length = series.length;
    if (length == 0) return 0;

    int accumulated = 0;
    for(int j = 0; j < length - 1; ++j)
      accumulated += Math.min(series[j + 1] - series[j], time);
    return accumulated + time;
  }
}