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.
1#include <vector>
2using namespace std;
3
4int findPoisonedDuration(vector<int>& timeSeries, int duration) {
5 int totalDuration = 0;
6 for (int i = 0; i < timeSeries.size(); i++) {
7 if (i == timeSeries.size() - 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#include <iostream>
17int main() {
18 vector<int> timeSeries = {1, 4};
19 int duration = 2;
20 cout << findPoisonedDuration(timeSeries, duration) << endl;
21 return 0;
22}This solution is a C++ adaptation of the algorithm that iterates over timeSeries to sum up the poison effects, carefully handling overlaps. It leverages a vector for input to utilize STL features.
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.