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.
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.