C++ O(N) solution with explanations


  • 0
    G
    class Solution {
    public:
    
        int findPoisonedDuration(vector<int>& timeSeries, int duration) 
        {
            int Result = 0;
            
            if(timeSeries.empty())
            {
                return (0);
            }
            
            //
            // B- the begining of the interval
            // E - the end of the interval
            //
            
            int B = timeSeries[0];
            int E = B + duration;
            
            for(int i = 1; i <= timeSeries.size(); ++i)
            {
                if(i == timeSeries.size())
                {
                    Result += E - B;
                    break;
                }
                
                if(timeSeries[i] >= E)
                {
                    //
                    // No intersection between current time
                    // and previous interval
                    //
                    
                    Result += E - B;
                    B = timeSeries[i];
                    E = B + duration;
                }
                else
                {
                    //
                    // There is an intersection:
                    // Add the previous interval duration to the result
                    // Make the new interval start at the end of the previous one
                    // and the end of the new interval is adjusted based on the current time + duration
                    // 
                    
                    Result += E - B;
                    B = E;
                    E = timeSeries[i] + duration;
                }
            }
            
            return Result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.