Teemo Attacking คำนวณเวลาสมพิษรวมใน C++

ในเกม LOL เทมโม่โจมตีแอชทำให้เป็นพิษ กำหนดเวลาโจมตี t[] (เรียงเพิ่ม) และระยะเวลาพิษ d หาเวลารวมที่แอชเป็นพิษ

ตัวอย่าง: t=[1,4], d=2 → 4 (เวลา 1-2 และ 4-5 ไม่ทับซ้อน)

วิธีแก้ปัญหา (Interval Merging)

1. ret = 0, currEnd = -1
2. วนแต่ละการโจมตี t[i]:
   • start = t[i], end = t[i] + d - 1
   • ถ้า currEnd < start: ret += end - start + 1, currEnd = end
   • มิฉะนั้น: ret += end - currEnd, currEnd = end
3. คืนค่า ret

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findPoisonedDuration(vector<int>& t, int d) {
        int ret = 0, currEnd = -1;
        int n = t.size();
        for (int i = 0; i < n; i++) {
            int start = t[i];
            int end = t[i] + d - 1;
            if (currEnd < start) {
                ret += end - start + 1;
                currEnd = end;
            } else {
                ret += end - currEnd;
                currEnd = end;
            }
        }
        return ret;
    }
};

int main() {
    vector<int> v = {1, 4};
    Solution ob;
    cout << ob.findPoisonedDuration(v, 2);
    return 0;
}

Input

[1,4] 2

Output

4