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
This C solution manages the end of the current poison effect period, adjusting it dynamically with each attack. It checks for overlapped periods and updates the total duration based on effective poisoning time.