O(n) Java Solution using same idea of merge intervals


  • 15

    The same idea as https://leetcode.com/problems/merge-intervals/
    Algorithm:

    1. Use two variable to record current start and end point.
    2. If the start of new interval is greater than current end, meaning NO overlapping, we can sum the current interval length to result and then update start and end.
    3. Otherwise just update the current end;
    public class Solution {
        public int findPosisonedDuration(int[] timeSeries, int duration) {
            if (timeSeries == null || timeSeries.length == 0 || duration == 0) return 0;
            
            int result = 0, start = timeSeries[0], end = timeSeries[0] + duration;
            for (int i = 1; i < timeSeries.length; i++) {
                if (timeSeries[i] > end) {
                    result += end - start;
                    start = timeSeries[i];
                }
                end = timeSeries[i] + duration;
            }
            result += end - start;
            
            return result;
        }
    }
    

  • 1
    R

    Python version:

    class Solution(object):
        def findPoisonedDuration(self, timeSeries, duration):
            if not timeSeries or len(timeSeries) == 0 or duration == 0:
                return 0
            result, start, end = 0, timeSeries[0], timeSeries[0] + duration
            
            for i in xrange(1, len(timeSeries)):
                if timeSeries[i] > end:
                    result += end - start
                    start = timeSeries[i]
                end = timeSeries[i] + duration
            result += end - start
            
            return result
    
    

  • 2

    The shining point isn't @shawngao's solution, but his ability to see the connections between problems.


  • 9

    Another angle to look at the problem -

        public int findPoisonedDuration(int[] timeSeries, int duration) {
            if (timeSeries.length == 0 || duration == 0) return 0; 
            int cnt = duration;
            for (int i = 1; i < timeSeries.length; i++)
                    cnt += Math.min(timeSeries[i] - timeSeries[i - 1], duration);
            return cnt; 
        }

  • 0

    Here is my solution. I personally prefer the solution dealing with each possible cases intuitively. Anyway, your solution is good enough and much conciser than mine. Thanks for sharing.

    public int findPoisonedDuration(int[] timeSeries, int duration) {
            if(timeSeries == null || timeSeries.length == 0 || duration <= 0) return 0;
            int res = 0, start = timeSeries[0], end = timeSeries[0] + duration;
            for(int i = 1; i < timeSeries.length; i ++){
                if(timeSeries[i] >= end){
                    res += end - start;
                    start = timeSeries[i];
                    end = timeSeries[i] + duration;
                }else{
                    res += timeSeries[i] - start;
                    start = timeSeries[i];
                    end = timeSeries[i] + duration;
                }
            }
            res += end - start;
            return res;
        }
    

  • 0
    R

    Mine:

    Kotlin

    fun findPoisonedDuration(timeSeries: IntArray?, duration: Int): Int {
        if (timeSeries == null || timeSeries.size == 0) return 0
    
        var sum = 0
        for (i in 1..timeSeries.size - 1) {
            sum += Math.min(timeSeries[i] - timeSeries[i - 1], duration)
        }
        return sum + duration
    }
    

    Java

    public int findPoisonedDuration(int[] timeSeries, int duration) {
            if(timeSeries == null || timeSeries.length == 0) return 0;
    
            int sum = 0;
            for(int i = 1; i < timeSeries.length; ++i) {
                sum += Math.min(timeSeries[i] - timeSeries[i-1], duration);
            }
            return sum+duration;
        }
    

  • 0
    L

    @zzhai ,I prefer this


  • 0
    H

    @richdyang love your answer,expilicity


  • 0
    S

    Share my solution, same idea. More code but more intuitive

    public class TeemoAttack {
    	public int findPoisonedDuration(int[] timeSeries, int duration) {
    		if (timeSeries.length == 0 || duration == 0) return 0;
    		int start = timeSeries[0];
    		int end = timeSeries[0] + duration;
    		int result = 0;
    		for (int i = 1; i < timeSeries.length; i++) {
    			if (timeSeries[i] < end) {
    				result += timeSeries[i] - start;
    				start = timeSeries[i];
    			}
    			else {
    				result += duration;
    				start = timeSeries[i];
    			}
    			end = timeSeries[i] + duration;
    		}
    		return result + duration;
    	}
    }
    

  • 0
    F

    From the angle of the game playing... My idea is a little difference, just count how many damage each attack can produce. If the current attack time plus duration smaller than the next attack time, then current attack can produce duration time damage( A full damage without any waste, awesome! ). If the current attack plus duration time will bigger than next attack time, which means the current attack can not produce full duration time damage, just produce the time difference damage between current attack time and next attack time. Update the total damage each time. Hhhhhaaa, an interesting explanation.

    public class Solution {
        public int findPoisonedDuration(int[] timeSeries, int duration) {
            if(timeSeries.length == 0) return 0;
            int count = 0;
            for(int i = 0;i<timeSeries.length-1;i++){
                if(timeSeries[i] + duration -1 >= timeSeries[i+1]){
                    count += timeSeries[i+1] - timeSeries[i];
                }
                else count+=duration;
            }
            return count + duration;
        }
    }
    

  • 0
    U

    There is no need to increase count at every time. Only when it is out of range.

        public int findPoisonedDuration(int[] timeSeries, int duration) {
            if(timeSeries.length==0) return 0;
            int count =0;
            int start = timeSeries[0];
            for(int i=1;i<timeSeries.length;i++){
                if(timeSeries[i]>timeSeries[i-1]+duration){
                    count+=timeSeries[i-1]+duration-start;
                    start=timeSeries[i];
                }
            }
            count+=timeSeries[timeSeries.length-1]+duration-start;
            return count;
        }
    

  • 0

    Sharing my solution, looking at the problem in a more intuitive perspective:

    • the previous duration has ended already: only count in the duration
    • the previous duration has not ended: refresh the duration. As with the previous duration, we only count in as long as the interval between these two attacks
    public class Solution {
        public int findPoisonedDuration(int[] timeSeries, int duration) {
            int sum = 0;
            for (int i = 1; i < timeSeries.length; i++) {
                if (timeSeries[i] - timeSeries[i - 1] >= duration) {
                    sum += duration;
                } else {
                    sum += timeSeries[i] - timeSeries[i - 1];
                }
            }
            return sum + (timeSeries.length > 0 ? duration : 0);
        }
    }
    

  • 0

    Keep adding duration to current time. Only two possibilities exist with this.

    • ts[i] > end : In this case, the all previous additions doesn't matter. It's a fresh start. So just add duration.
    • ts[i] <= end : In this case, curEnd = ts[i] + duration is always greater than previous end. The effective increase is just the difference of this.
    public int findPoisonedDuration(int[] ts, int duration) {
        int result = 0, end = -1;
        for(int i = 0; i < ts.length; i++) {
            int curEnd = ts[i] + duration - 1;
            result += ts[i] > end ? duration : curEnd - end;
            end = curEnd;
        }
        return result;
    }

Log in to reply
 

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