题目描述

在《英雄联盟》的世界中，有一个叫“提莫”的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）
进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。

样例

输入: [1,4], 2
输出: 4
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
第 4 秒初，提莫再次攻击艾希，使得艾希获得另外 2 秒中毒时间。所以最终输出 4 秒。

(区间合并) $O(n)$

1.这是一道区间合并的变形题，特别的是只给出区间的左端点，并且已经排好序，美滋滋；

2.从前到后维护start，end，对于每段区间s[i],e[i],if(end<s[i])更新start，end，注意判断边界st！=-1是才能累加res
  并求出这段区间的数个数累加res，否则更新end=max(end,e[i]);

3.注意只有在更新start，end的时候才累加res，这样会忽视不断扩大的end维护的区间，所以最后res+=end-start+1，
  这一步不要忘记；

C++ 代码

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
    int n=timeSeries.size(),start=-1,end=-1;
    if(!n) return 0;
    int res=0;
    for(int i=0;i<n;i++)
    {
        int s=timeSeries[i],e=timeSeries[i]+duration-1;
        if(s>end)
        {
            if(start!=-1) res+=end-start+1;
            start=s,end=e;
        }
        else end=max(end,e);
    }
    res+=end-start+1;
    return res;
    }
};

算法2

(单次扫描) $O(n)$

1. 考虑相邻两个攻击时间点 A[i] 和 A[i + 1] 以及中毒持续时间 t;

2. 如果 A[i] + t <= A[i + 1]，那么在第 i + 1 次攻击时，第 i 次攻击造成的中毒的持续时间已经结束，res+=t;

3.如果 A[i] + t > A[i + 1]，那么在第i+1次攻击时，第i次攻击的中毒仍然在持续，不可累加， res+= A[i + 1]-A[i]。

4.综上，res+=min(A[i+1]-A[i],t);

C++

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
    int n=timeSeries.size();
    if(n==0) return 0;
    int total=0;
    for(int i=0;i<n-1;i++)
     total+=min(timeSeries[i+1]-timeSeries[i],duration);

     return total+duration;

    }
};