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.
1using System;
2
3public class TeemoAttacking {
4 public int FindPoisonedDuration(int[] timeSeries, int duration) {
5 int totalDuration = 0;
6 for (int i = 0; i < timeSeries.Length; i++) {
7 if (i == timeSeries.Length - 1 || timeSeries[i + 1] >= timeSeries[i] + duration) {
8 totalDuration += duration;
9 } else {
10 totalDuration += timeSeries[i + 1] - timeSeries[i];
11 }
12 }
13 return totalDuration;
14 }
15
16 public static void Main(string[] args) {
17 TeemoAttacking ta = new TeemoAttacking();
18 int[] timeSeries = {1, 4};
19 int duration = 2;
20 Console.WriteLine(ta.FindPoisonedDuration(timeSeries, duration));
21 }
22}The C# version uses similar logic as other languages to sum the poisoned seconds based on whether attacks cause duration resets. The straightforward loop allows for simple condition checks and accumulation.
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.
1using namespace std;
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
if (timeSeries.empty()) return 0;
int totalDuration = 0;
int end = timeSeries[0] + duration;
for (int i = 1; i < timeSeries.size(); ++i) {
if (timeSeries[i] < end) {
totalDuration += timeSeries[i] - timeSeries[i - 1];
} else {
totalDuration += duration;
}
end = timeSeries[i] + duration;
}
totalDuration += duration;
return totalDuration;
}
#include <iostream>
int main() {
vector<int> timeSeries = {1, 4};
int duration = 2;
cout << findPoisonedDuration(timeSeries, duration) << endl;
return 0;
}The C++ solution computes poison effects by determining how much of each attack overlaps with the poison period of previous attacks. It dynamically updates the 'end' time of poison for each attack.