Sponsored
Sponsored
This approach involves iteratively calculating the poison effect duration from the attack times given in timeSeries. The idea is to maintain a running total of poison duration impacts caused by each attack, making adjustments for overlaps where a new attack resets the poison timer.
Time Complexity: O(n), where n is the number of attack times in timeSeries.
Space Complexity: O(1), as we only use a limited amount of extra space.
1function findPoisonedDuration(timeSeries, duration) {
2 let totalDuration = 0;
3 for (let i = 0; i < timeSeries.length; i++) {
4 if (i === timeSeries.length - 1 || timeSeries[i + 1] >= timeSeries[i] + duration) {
5 totalDuration += duration;
6 } else {
7 totalDuration += timeSeries[i + 1] - timeSeries[i];
8 }
9 }
10 return totalDuration;
11}
12
13console.log(findPoisonedDuration([1, 4], 2));In JavaScript, the function implements a similar logic by iterating over the attack time points, evaluating whether the poison period should be added as a full duration or adjusted due to an overlap from subsequent attacks.
In this approach, we utilize a dynamic programming technique to handle overlapping intervals. The essence here is to consider the overlap between poison effects and adjust the ending intervals of these periods dynamically.
Time Complexity: O(n) since we iterate through timeSeries just once.
Space Complexity: O(1) due to using minimal additional memory.
1
public class TeemoAttacking {
public int FindPoisonedDuration(int[] timeSeries, int duration) {
if (timeSeries.Length == 0) return 0;
int totalDuration = 0;
int end = timeSeries[0] + duration;
for (int i = 1; i < timeSeries.Length; ++i) {
if (timeSeries[i] < end) {
totalDuration += timeSeries[i] - timeSeries[i - 1];
} else {
totalDuration += duration;
}
end = timeSeries[i] + duration;
}
totalDuration += duration;
return totalDuration;
}
public static void Main(string[] args) {
TeemoAttacking ta = new TeemoAttacking();
int[] timeSeries = {1, 4};
int duration = 2;
Console.WriteLine(ta.FindPoisonedDuration(timeSeries, duration));
}
}This C# solution leverages updating end times dynamically, accounting for overlaps and sequential attacks. It calculates the total poisoned time efficiently.