This problem appeared in the coding round of a company(cannot name) which was hiring interns at 100k stipend(India). This was the toughest problem of the round. I have seen similar problems at other contests but do not know the optimal solution.

Statement:

You have a shield whose power increases by 1 every second. You are given N time intervals when a Missile is fired at you. You can face it if your shield has enough power by then, or you can use counter-Missile to divert the incoming missile and decide not to take the damage. If you decide to take the damage, the power of the shield reduces by the power of incoming missile. The power of the shield should remain non-negative.

The shield starts generating power from time = 0.

Test Case:

N = 3 (Number of missiles fired at you)

Details of N Missiles.

Time -> Damage

20 ->20

21 ->4

22 ->3

It is optimal to use counter-missile on the first attack although you had enough power to take the attack.

So the minimum number of missiles that you should use is 1

Initial power = 20 since time = 20(You must have gained 1, 20 times)

N = 1 , Use counter-Missile : Power remaining: 20

N = 2; Take the attack : Power remaining : 17

N = 3, Take the attack : Power remaining : 15.

The task is to find the minimum number of missiles.

So, the answer for the case : 1.

Constraints:

N <= 1e5;

Damage <= 1e9 (I was surprised here).

The solution seems DP-ish but I dont know how to solve for Damage <= 1e9.